0
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – Steven
    Commented Aug 18, 2021 at 23:50
  • $\begingroup$ 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}$. $\endgroup$
    – Frank
    Commented Aug 18, 2021 at 23:52
  • $\begingroup$ 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 ;) $\endgroup$
    – Steven
    Commented Aug 18, 2021 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.