Halting problem with minimal Turing Machine as promised input

Question

Consider the following Turing Machine A.

Input: Turing Machine M that recognizes some language L(M)

Output:

• If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same language L(M)), then A returns whether M halts on all inputs or not.
• Otherwise, A returns either YES or NO (which can be wrong).

(Note that A must always halt.)

How can we prove that A does not exist?

I believe that A does not exist, but could not prove it myself or find a proof in the literature. Note that if A must return the correct answer for all possible M, then this is simply the halting problem. Here, we allow it to return correct answers only for minimal M.

• Noah Schweber: This is likely to not have a "coarse" proof, but rather depend on usually-ignored details of the way we encode Turing machines (see e.g. the issues brought up in this old answer of mine). For what it's worth I do suspect that the answer is negative for all acceptable enumerations of Turing machines.
• Denis: If you allow almost-minimality, ie minimal up to a fixed additive constant, then by adapting the proof of undecidability of halting we can show it's not possible. Strict minimality seems to pose a challenge though.

Answer 1

This is a partial answer, showing that for one "reasonable" (but not quite standard) Turing Machine model there is such a machine $A$. On the other hand, in this model there is not a Turing Machine that meets a very similar set of requirements.

---

The Turing Machine model. We take the standard model with one modification. In the standard model, during an execution, if the machine reaches a configuration for which no transition is defined in the transition table, the standard model specifies that the machine halts in the current state. Our modified model specifies that in this situation, instead, there is an implicit transition that does nothing: the machine stays in the current state, without changing the tape contents or the location of the tape head, so, instead of halting, the machine loops forever (in the same state).

In order to halt, the machine must instead explicitly enter a designated halt state (either a designated "reject" state or a designated "accept" state). This definition preserves the class of Turing Recognizable languages, and also preserves the class of Decidable languages. In that sense it is "reasonable".

With this modification, we then further assume that, in determining minimality, the primary key is the number of transitions in the transition table. That is, for any minimal machine there is no machine that accepts the same language and has fewer transitions.

We show the following two lemmas:

Lemma 1. In this model, there is a machine $A$ with the behavior specified by OP:

input: $\langle M\rangle$

output:

• If $M$ is minimal, then $A$ halts, returning YES if $M$ halts on all inputs and NO otherwise.
• If $M$ is not minimal, then $A$ halts (returning anything).

Lemma 2. In this model, there is no Turing machine $B$ with the following behavior:

input: $\langle M, x\rangle$, where $M$ is a Turing Machine and $x$ is a possible input for $M$

output:

• If $M$ is minimal, then $B$ halts, returning YES if $M$ halts on $x$, and NO otherwise.
• If $M$ is not minimal, there is no requirement on $B$ (it might not even halt).

Before we prove the lemmas, we prove the following claim:

Claim 1. For any minimal machine $M$, the language of $M$ is the set of inputs on which $M$ halts.

Proof of Claim 1. Recall that we assume that every TM has an accept state and a reject state, and that the model specifies that if $M$ is executing and enters a configuration for which no transition is defined, the execution continues in an infinite loop (in the same configuration). If this happens, by definition, the machine does not accept the input, so the input is not in the language.

Given any TM $M$, consider modifying the transition table of $M$ as follows: for every transition that leads to the reject halt state, remove the transition from the transition table.

This modification preserves the language of the machine, because any input $x$ that leads to such a transition is not in the language of the $M$ (as $M$ rejects $x$), and is not in the language of the modified machine (as that machine runs forever on $x$).

If this modification in fact changes $M$, then $M$ is not minimal, because the modified machine has a smaller transition table. Hence, no minimal machine has a transition into the reject state. That is, on any input, the machine either halts and accepts the input, or the machine runs forever. This proves Claim 1. $~~~\Box$

Proof of Lemma 1. From Claim 1, it follows that a given minimal machine $M$ halts on all inputs if and only if it accepts all inputs. This uniquely determines the language of $M$ (to be $\Sigma^*$). Consequently, there is only one minimal machine that halts on all inputs. So the desired machine $A$ can simply accept the encoding of this one machine, and no other. $~~~\Box$

Proof of Lemma 2. Suppose for contradiction that $B$ exists. Consider the following Turing Machine $D$:

Turing Machine $D$ on input $\langle M\rangle$:

1. Run $B$ on $\langle M, \langle M\rangle \rangle$. Accept if and only if $B$ returns NO.

By the assumptiond on $B$, Turing Machine $D$ has the following property:

• If $M$ is minimal, then $\langle M \rangle \in L(D)$ if and only if $M$ doesn't halt on input $\langle M\rangle$.

By Claim 1, it follows that

• If $M$ is minimal, then $\langle M \rangle \in L(D)$ if and only if $\langle M\rangle \not\in L(M)$.

Now let $D^*$ be the minimal TM equivalent to $D$ (so $L(D) = L(D^*)$). Substituting $D^*$ for $M$ above,

• Because $D^*$ is minimal, $\langle D^*\rangle \in L(D)$ if and only if $\langle D^*\rangle \not\in L(D^*)$.

But this contradicts $L(D) = L(D^*)$. $~~~\Box$

I suspect that Lemma 2 holds for standard TM models as well, and may be easier to show than what OP asks for.

Answer 2

For any TM M that decides some language L(M), there is a TM M’ that, from a blank tape, generates the characteristic function in the form of a bit-sequence: e.g., 0 0 1 0 1 1 1 0 ... This sequence, which tells us for each input word whether it is in L(M) or not, is compressible via M’.

Theorem in the literature: For any recursive time bound t() of your choice, there exist compressible strings and sequences that are t-bounded incompressible.

Suppose now that halting TM A exists. This means that A has a recursive time bound t(). Consider then, via the theorem, a t-bounded incompressible sequence such that M’, and consequently M, render machine A ineffective. Hence, A does not exist after all.

(Something like the above might help? Definitely neeeds polishing.)

• Noah Schweber: "I believe you can show that A* cannot meet your specification" How, precisely?