1
$\begingroup$

It can be shown that Turing machines, μ-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing machines.

Isn't it much easier to argue that the function halts below cannot exist in e.g. python since then I would be able to write the following program which is a contradiction.

def halts(source):
  ...

if __name__ == "__main__":
  this_file = open(__file__)
  if halts(this_file.read()):
    while True:
      pass
  else:
    return 1

Why is this proof not as good as the TM diagonal argument?

Edit: I read https://cs.stackexchange.com/a/94235/119946

OK, fine. This proves that the halting problem can't be solved for code written in any programming language that has a get_source_code_of_current_function() API. However, my favorite programming language doesn't have such an API. So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows? Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

I mean by that argument I can say the TM proofs only shows that the halting problem cannot be decided by Turing machines, but does not show anything about python. Isn't the crucial part, that (as I wrote) TM and modern programming languages can compute/decide the same problems? If one can decide the halting problem, then all other can do so as well and vice versa.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 1) A good thing about Turing machines is that they are simple. In your code, you need to formally define what means def, return, open, read, __name__, ==, etc. etc. Sounds like a lot of pain. 2) Python is Turing-complete, i.e. you can simulate TM with python. The halting problem says that you can't say whether the TM halts $\implies$ whether the simulation halts $\implies$ whether your python program halts. $\endgroup$
    – user114966
    Oct 23, 2020 at 16:30
  • $\begingroup$ I can be shown that TMs can simulate register machines e.g. modern computers. Hence, you can run python on them. The keywords you mentioned are already defined in the python spec. $\endgroup$
    – Manuel Schmidt
    Oct 23, 2020 at 16:36
  • $\begingroup$ I don't understand the point of the first part of your comment. You've written I can say the TM proofs only shows that the halting problem cannot be decided by Turing machines, but does not show anything about python. I explained it does show the same thing about Python. The keywords you mentioned are already defined in the python spec sure, they probably are. And all these definitions must be taken into account when you try to proof stuff about your code. You need to formally define the semantics, and instead of 1 page for TM it'll be hundreds? of pages of specification. $\endgroup$
    – user114966
    Oct 23, 2020 at 16:41
  • $\begingroup$ I don't say you can't show that halting problem is undecidable for Python. I'm saying that 1) It's simpler to show that for TM. 2) It implies result for Python. $\endgroup$
    – user114966
    Oct 23, 2020 at 16:43
  • $\begingroup$ OK, then I agree with you on 2). You missed the I mean by that argument, ... part while quoting me. I disagreed with the cited answer, and with 1) as my "proof" above is easier than the diagonal argument. The spec is already written and it follows whether python halts $\implies$ wether the TM simulation of it halts $\implies$ whether the TM halts. $\endgroup$
    – Manuel Schmidt
    Oct 23, 2020 at 16:50

2 Answers 2

Reset to default
2
$\begingroup$

The goal we really want is a total impossibility result:

There is no reasonable model of computation which can solve its own halting problem.

Church's thesis says that all the usual models (Turing machines, $\mu$-recursion, Python, etc.) are appropriately equivalent and so a proof in any one system should be convincing. However, initially at least we might not have total faith in the thesis; more generally, maybe we just want to avoid leaning on it too much as a matter of principle. In either case, what we then want is a proof of the unsolvability of the halting problem in the sense of some model of computation so basic that that same argument obviously lifts to any other model. For example, since files aren't a thing that all computation models interact with, we probably don't want to use them.

Turing machines are a sweet spot in this sense: they only deal with very simple objects (functions on natural numbers) which every model of computation will have, and they're intuitive to work with.

Improve this answer
$\endgroup$
3
$\begingroup$

You could totally do that, but there are some consequences it's worth being aware of.

TM proofs only show difficulty of the halting problem for TMs, but here's a crucial thing that you might be overlooking: it is easy to implement a simulator of a TM in any language of one's choice. That can probably be done in a few dozen lines of code and it is conceptually straightforward. This lets us very easily see that the halting problem is also hard in those other languages, too.

The same is not true for Python. You can't write a Python interpreter in a few dozen lines of code.

Let me try it another way.

Some languages don't have a __file__ global variable or anything with similar semantics. That makes it unclear whether your result applies to other languages.

Sure, we could try to write down a reduction. In some other language, we could build a Python interpreter that supports __file__. But that's not a trivial exercise! We might need to implement a filesystem, library functions that interact with the filesystem, a parser for Python code, an interpreter for Python code, and so on. Nothing you can code up in a few hours, and it's not trivial to construct such a reduction.

Now, sure, your argument does work, so it's just a matter of taste which you prefer. I am showing you some reasons why someone might prefer the TM proof. If you prefer the Python proof, that's fine. That's your choice. I just want you to be aware of the implications of your choice, and for you to understand all of the steps of reasoning that you have to go through, if you want to use it to draw conclusions about other programming languages. Arguably your choice makes some parts of the reasoning easier, and some parts (the application to other programming languages) harder.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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