Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
1  
Example in code then? –  Masterminder Dec 9 '12 at 0:05
1  
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
show 2 more comments

1 Answer

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.