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
    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.2012-12-09
  • 1
    Example in code then?2012-12-09
  • 1
    Again quite complicated, too complicated for a satisfactory answer.2012-12-09
  • 0
    if you have any ideas or could explain in words , would help2012-12-09
  • 0
    Take a look at the following file http://www.math.psu.edu/simpson/courses/math457/trakh.ps2012-12-09
  • 0
    this does not work for me :(2012-12-09
  • 0
    www.math.psu.edu/simpson/courses/math457/trakh.ps2012-12-09

1 Answers 1