What does $w' := <M'>$ mean in the context of the Halting Problem?

153 Views Asked by At

I am studying the Halting Problem and I came across the following notation. I am not sure what it means. The context is as follows:

To prove that the Halting Problem is undecidable, we employ proof by contraction. Assume that the language $K = \{w \in \{0,1\}^* | M_w \ \text{stops for input w}\}$, is decidable. This means that the characteristic function $\chi_K$ is computable using a Turing Machine $M$. Now we can construct a Turing Machine $M'$ that simulates $M$. When the output is $0$, the $M$ stops and when the output is $1$, then $M$ goes in an endless loop. Let $w' := <M'>$ ...

What does $w' := <M'>$ mean in this context? Is it just that $M'$ is a Turing Machine that is encoded by $w'$?

1

There are 1 best solutions below

0
On BEST ANSWER

Notice that Turing Machines are powerful enough to simulate other Turing Machines. We encode Turing Machines $M$ as words $\langle M \rangle$ and we can formulate the Halting Problem as a word problem for the language $L=\{\langle M \rangle \epsilon \langle \omega \rangle\ |\ M \text{ halts on input } \omega\}$ whereby $\langle M \rangle$ and $\langle \omega \rangle$ are encodings for $M$ and $\omega$ and $\epsilon$ is a separator.

First denote $(M, \omega)$, whereby $M$ is a Turing Machine and $\omega$ some word of our input alphabet of $M$. Then the encoding of such a pair is often denoted by $\langle M, \omega \rangle$.

Since $\omega' \in \{0,1\}^*$ (which is our word encoding for which we could also write $\langle \omega' \rangle$), and $\langle M' \rangle$ denotes the encoding of the Turing Machine $M'$, it is indeed encoded by the binary word $\omega'$.

To summarize, we write $\langle M' \rangle$ to denote the encoding of the Turing Machine $M'$, and since $\omega'$ is an encoded word, $\omega' := \langle M' \rangle$ says that the encoding of $M'$ (which is $\langle M' \rangle)$ is given by $\omega'$.