# First Order Logic Example of Halting Problem

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!

-
If 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. –  André Nicolas Dec 9 '12 at 0:04
Example in code then? –  Masterminder Dec 9 '12 at 0:05
Again quite complicated, too complicated for a satisfactory answer. –  André Nicolas Dec 9 '12 at 0:08
if you have any ideas or could explain in words , would help –  Masterminder Dec 9 '12 at 0:09
Take a look at the following file math.psu.edu/simpson/courses/math457/trakh.ps –  boumol Dec 9 '12 at 9:11

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
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?