The problem {x ∣ Tx(x)=1} is undecidable

[mathmari]

Hey!

I want to prove that the problem $\{x\mid T_x(x)=1\}$ is undecidable.

Let $A=\text{HALT}=\{x\in \mathbb{N}_0\mid T_x(x)\downarrow\}$ and $B$ the above problem.

We want to construct a "translation" of $A$ to $B$, i.e., we want to construct a computable function $f$ such that $x\in A\Leftrightarrow f(x)\in B$.

Could you give me some hints how we can find that function? (Wondering)

 

[Evgeny.Makarov]

I want to prove that the problem $\{x\mid T_x(x)=1\}$ is undecidable.

Could you remind what $T_x(y)$ is? I know about Kleene's T predicate, but it has three arguments.

 

[mathmari]

Could you remind what $T_x(y)$ is? I know about Kleene's T predicate, but it has three arguments.

$T_x(y)$ is the Turing machine with code $x$ and input $y$.

 

[Evgeny.Makarov]

Given a machine, $f$ should change it so that if it halts, it outputs 1.

 

[mathmari]

Given a machine, $f$ should change it so that if it halts, it outputs 1.

But how could we define the function so that it does that? (Wondering)

 

[Evgeny.Makarov]

A machine halts when it enters the accepting or rejecting state. Replace those states with ordinary state $q_0$ throughout the program (set of instructions) and add a new block of instructions so that when the machine is in $q_0$, it erases the content of the tape and writes 1 on it.

Now there is a question how to erase the content of the tape. How does the machine know that beyond a certain position all cells contain the blank symbol? The original program $M$ can be modified so that it counts the number of steps it takes. That is, the original program is not simply run as a subroutine, but rather interpreted, and the number of steps is counted. Then the target program (i.e., the output of $f(\lceil M\rceil)$ erases as many cells as the number of steps taken by $M$ and then writes 1. If $M$ does not stop, $f(\lceil M\rceil)$ does not stop either. This all assumes I understood correctly that $T_x(x)=1$ means that the machine with code $x$ and input $x$ outputs 1.

I recommend reading section 5.3 "Mapping Reducibility" in the Sipser's book to see more examples of reductions.