I am trying to understand the halting problem better. What would be a few examples of some first order formulas that express a halting problem? Any responses would be appreciated! Thank you!
First Order Logic Example of Halting Problem
-
0If you want a sentence in the language of *arithmetic*, such a sentence is terribly complicated, since we have to encode Turing machine computations using only $+$, $\times$, and logical symbols. – 2012-12-09
-
1Example in code then? – 2012-12-09
-
1Again quite complicated, too complicated for a satisfactory answer. – 2012-12-09
-
0if you have any ideas or could explain in words , would help – 2012-12-09
-
0Take a look at the following file http://www.math.psu.edu/simpson/courses/math457/trakh.ps – 2012-12-09
-
0this does not work for me :( – 2012-12-09
-
0www.math.psu.edu/simpson/courses/math457/trakh.ps – 2012-12-09
1 Answers
Just think about 'Turing machines' as programs of some programming language. Then the halting problem would mean such a program $\mathcal H$ which inputs a source code of a program $\mathcal P$ and an input word $w$, and outputs 'YES' or 'NO' according that whether $\mathcal P$ halts on input $w$ or falls in infinite cycle.
If it existed, $\mathcal H$ would have a source code, and we can hack it (producing $\mathcal H'$) so that falls in infinite cycle at all places where $\mathcal H$ displayed 'YES', and before processing the input strings, overwrite the second one with the first one double. Say, there is a special character , to split the inputs of $\mathcal H$, input1 and input2, and it is important to refer to it somehow in the language, say by a constant term comma. Then before any use of input2, insert the line
input2:=input1+ comma +input1;
So that, if $p$ is the source code of $\mathcal P$, then $\mathcal H'(p,w)$ doesn't halt $\iff \mathcal H(p,(p,p))=$'YES' $\iff\ \mathcal P$ halts on input $p,p$.
Now $\mathcal P:=\mathcal H'$ and $w:={\rm code}(\mathcal H')$ for the contradiction: does or does not $\mathcal H'(w,w)$ halt?