<p>This is a partial answer, showing that for one &quot;reasonable&quot; (but not quite standard) Turing Machine model there is such a machine <span class="math-container">$A$</span>.  On the other hand, in this model there is <em>not</em> a Turing Machine that meets a very similar set of requirements.</p>
<hr />
<p><strong>The Turing Machine model.</strong> <em>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).</em></p>
<p>In order to halt, the machine must instead explicitly enter a designated halt state (either a designated &quot;reject&quot; state or a designated &quot;accept&quot; state).  This definition preserves the class of Turing Recognizable languages, and also preserves the class of Decidable languages.  In that sense it is &quot;reasonable&quot;.</p>
<p>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.</p>
<p>We show the following two lemmas:</p>
<p><strong>Lemma 1.</strong> <em>In this model, there is a machine <span class="math-container">$A$</span> with the  behavior specified by OP:</em></p>
<blockquote>
<p><strong>input:</strong> <span class="math-container">$\langle M\rangle$</span></p>
<p><strong>output:</strong></p>
<ul>
<li><em>If <span class="math-container">$M$</span> is minimal, then <span class="math-container">$A$</span> halts, returning YES if <span class="math-container">$M$</span> halts on all inputs and NO otherwise.</em></li>
<li><em>If <span class="math-container">$M$</span> is not minimal, then <span class="math-container">$A$</span> halts (returning anything).</em></li>
</ul>
</blockquote>
<p><strong>Lemma 2.</strong> <em>In this model, there is no Turing machine <span class="math-container">$B$</span> with the following behavior:</em></p>
<blockquote>
<p><strong>input:</strong> <em><span class="math-container">$\langle M, x\rangle$</span>, where <span class="math-container">$M$</span> is a Turing Machine and <span class="math-container">$x$</span> is a possible input for <span class="math-container">$M$</span></em></p>
<p><strong>output:</strong></p>
<ul>
<li><em>If <span class="math-container">$M$</span> is minimal, then <span class="math-container">$B$</span> halts, returning YES if <span class="math-container">$M$</span> halts on <span class="math-container">$x$</span>, and NO otherwise.</em></li>
<li><em>If <span class="math-container">$M$</span> is not minimal, there is no requirement on <span class="math-container">$B$</span> (it might not even halt).</em></li>
</ul>
</blockquote>
<p>Before we prove the lemmas, we prove the following claim:</p>
<p><strong>Claim 1.</strong> <em>For any minimal machine <span class="math-container">$M$</span>, the language of <span class="math-container">$M$</span> is the set of inputs on which <span class="math-container">$M$</span> halts.</em></p>
<p><em>Proof of Claim 1.</em> Recall that we assume that every TM has an accept state and a reject state, and that the model specifies that if <span class="math-container">$M$</span> 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.</p>
<p>Given any TM <span class="math-container">$M$</span>, consider modifying the transition table of <span class="math-container">$M$</span> as follows: <em>for every transition that leads to the reject halt state, remove the transition from the transition table</em>.</p>
<p>This modification preserves the language of the machine, because any input <span class="math-container">$x$</span> that leads to such a transition is not in the language of the <span class="math-container">$M$</span> (as <span class="math-container">$M$</span> rejects <span class="math-container">$x$</span>), and is not in the language of the modified machine (as that machine runs forever on <span class="math-container">$x$</span>).</p>
<p>If this modification in fact changes <span class="math-container">$M$</span>, then <span class="math-container">$M$</span> 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. <span class="math-container">$~~~\Box$</span></p>
<p><em>Proof of Lemma 1.</em>  From Claim 1, it follows that a given minimal machine <span class="math-container">$M$</span> halts on all inputs if and only if it accepts all inputs.  This uniquely determines the language of <span class="math-container">$M$</span> (to be <span class="math-container">$\Sigma^*$</span>).  Consequently, there is only one minimal machine that halts on all inputs.  So the desired machine <span class="math-container">$A$</span> can simply accept the encoding of this one machine, and no other. <span class="math-container">$~~~\Box$</span></p>
<p><em>Proof of Lemma 2.</em> Suppose for contradiction that <span class="math-container">$B$</span> exists.
Consider the following Turing Machine <span class="math-container">$D$</span>:</p>
<blockquote>
<p>Turing Machine <span class="math-container">$D$</span> on input <span class="math-container">$\langle M\rangle$</span>:</p>
<ol>
<li>Run <span class="math-container">$B$</span> on <span class="math-container">$\langle M, \langle M\rangle \rangle$</span>.  Accept if and only if <span class="math-container">$B$</span> returns NO.</li>
</ol>
</blockquote>
<p>By the assumptiond on <span class="math-container">$B$</span>, Turing Machine <span class="math-container">$D$</span> has the following property:</p>
<ul>
<li>If <span class="math-container">$M$</span> is minimal, then <span class="math-container">$\langle M \rangle \in L(D)$</span> if and only if <span class="math-container">$M$</span> doesn't halt on input <span class="math-container">$\langle M\rangle$</span>.</li>
</ul>
<p>By Claim 1, it follows that</p>
<ul>
<li>If <span class="math-container">$M$</span> is minimal, then <span class="math-container">$\langle M \rangle \in L(D)$</span> if and only if <span class="math-container">$\langle M\rangle \not\in L(M)$</span>.</li>
</ul>
<p>Now let <span class="math-container">$D^*$</span> be the minimal TM equivalent to <span class="math-container">$D$</span> (so <span class="math-container">$L(D) = L(D^*)$</span>).
Substituting <span class="math-container">$D^*$</span> for <span class="math-container">$M$</span> above,</p>
<ul>
<li>Because <span class="math-container">$D^*$</span> is minimal, <span class="math-container">$\langle D^*\rangle \in L(D)$</span> if and only if <span class="math-container">$\langle D^*\rangle \not\in L(D^*)$</span>.</li>
</ul>
<p>But this contradicts <span class="math-container">$L(D) = L(D^*)$</span>.  <span class="math-container">$~~~\Box$</span></p>
<p>I suspect that Lemma 2 holds for standard TM models as well, and may be easier to show than what OP asks for.</p>

CC BY-SA 4.0
2024-09-12T21:32:16.613Z
2024-09-14T23:17:38.063Z
2024-09-14T23:17:38.063Z
Neal Young
<p>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’.</p>
<p>Theorem in the literature: For any recursive time bound t() of your choice, there exist compressible strings and sequences that are  t-bounded incompressible.</p>
<p>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.</p>
<p>(Something like the above might help? Definitely neeeds polishing.)</p>

CC BY-SA 4.0
2024-09-07T04:10:43.383Z
"I believe you can show that A* cannot meet your specification" How, precisely?
Noah Schweber
CC BY-SA 4.0
2024-09-06T22:03:24.240Z
2024-09-07T22:02:52.467Z
2024-09-07T22:02:52.467Z
Edgar Daylight
<p>Consider the following Turing Machine A.</p>
<p>Input: Turing Machine M that recognizes some language L(M)</p>
<p>Output:</p>
<ul>
<li>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.</li>
<li>Otherwise, A returns either YES or NO (which can be wrong).</li>
</ul>
<p>(Note that A must always halt.)</p>
<p><strong>How can we prove that A does not exist?</strong></p>
<p>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.</p>

CC BY-SA 4.0
2024-09-07T21:12:54.303Z
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](https://mathoverflow.net/questions/361862/what-are-some-examples-of-theorem-requiring-highly-subtle-hypothesis/361870#361870)). For what it's worth I do suspect that the answer is negative for all *acceptable* enumerations of Turing machines.
Noah Schweber
CC BY-SA 4.0
2024-09-08T12:22:13.970Z
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.
Denis
<cc.complexity-theory><computability><turing-machines><halting-problem>
Halting problem with minimal Turing Machine as promised input
BookH
# Halting problem with minimal Turing Machine as promised input

(Asked by: username_0 on 2024-09-06)

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.

**Tags:** cc.complexity-theory, computability, turing-machines, halting-problem
> **Comments:**
> **username_1**: 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](https://mathoverflow.net/questions/361862/what-are-some-examples-of-theorem-requiring-highly-subtle-hypothesis/361870#361870)). For what it's worth I do suspect that the answer is negative for all *acceptable* enumerations of Turing machines.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2024-09-12. Score: 2

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 by username_4 on 2024-09-06. Score: -3

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.)

> **Comments:**
> **username_1**: "I believe you can show that A* cannot meet your specification" How, precisely?  

---

