0
$\begingroup$

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!

  • 0
    www.math.psu.edu/simpson/courses/math457/trakh.ps2012-12-09

1 Answers 1

1

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?