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

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion focuses on proving the undecidability of the problem {x | T_x(x) = 1} by constructing a computable function that translates the HALT problem into this problem. Participants clarify that T_x(y) refers to a Turing machine with code x and input y, and they explore how to modify a machine to ensure it outputs 1 when it halts. Suggestions include altering the machine's states and adding instructions to erase tape content and write 1 based on the number of steps taken. The conversation emphasizes the importance of understanding the mechanics of Turing machines in this context. Overall, the goal is to establish a clear reduction from the HALT problem to demonstrate the undecidability of the target problem.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
mathmari said:
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.
 
Evgeny.Makarov said:
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$.
 
Given a machine, $f$ should change it so that if it halts, it outputs 1.
 
Evgeny.Makarov said:
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)
 
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.
 
Back
Top