# Where is the error in this logic for halting Turing machines?

Let $$\mathbb{H}$$ be the set of all Turing machines that halt on all inputs. Consider the following Turing machine $$T$$. On input $$\langle S \rangle$$ where $$S \in \mathbb{H}$$ (note that the angle brackets indicate a string encoding of $$S$$), $$T$$ does the following:

1. Simulate $$S$$ on $$\langle S \rangle$$.
2. If $$S$$ accepts, reject. If $$S$$ rejects, accept.

Because $$S \in \mathbb{H}$$, $$S$$ will always halt. Thus, $$T$$ will always halt, which implies $$T \in \mathbb{H}$$. Note that $$T$$ decides the language

$$\{\langle S \rangle \mid \text{S \in \mathbb{H} and S rejects \langle S \rangle}\}.$$

But $$T$$ accepts $$\langle T \rangle$$ if and only if $$T$$ rejects $$\langle T \rangle$$—this is a contradiction. Where is the error in this logic?

It is false that $$T$$ decides the language $$L = \{\langle S \rangle \mid \text{S \in \mathbb{H} and S rejects \langle S \rangle}\}.$$
In particular consider a turing machine $$M$$ that does not halt on all inputs but halts and rejects on input $$\langle M \rangle$$. Then $$T(\langle M \rangle)$$ accepts but $$\langle M \rangle$$ is not in $$L$$ since $$M \not\in \mathbb{H}$$.
I just realized where I went wrong. The Turing machine $$T$$ that I gave does not actually exist.
In particular, I required that $$S \in \mathbb{H}$$ for an input $$\langle S \rangle$$. But this implicitly tasks $$T$$ with verifying that $$S \in \mathbb{H}$$ before executing steps 1 and 2. This requires $$T$$ to solve the halting problem (or some variant of it).
• The Turing machine $T$ you describe does exist. You are requiring $T$ to behave in a certain way when its input is from $\mathbb{H}$ (and you impose no requirement when the input is not from $\mathbb{H}$). There is no need for $T$ to verify that the input is from $\mathbb{H}$. Aug 18, 2021 at 23:50
• I was being unclear. I meant that $T$ only executes steps 1 and 2 if the input is of the form $\langle S \rangle$ where $S \in \mathbb{H}$. Aug 18, 2021 at 23:52
• I see. Then I agree that your argument assumes the existence of a machine $T$ that is powerful enough to solve the halting problem and uses this fact to conclude that the halting problem is decidable, which is not very surprising ;) Aug 18, 2021 at 23:53