10 ms·

Did Turing prove the undecidability of the halting problem?

81 points by vitplister 2y ago

kouru225 2y ago
[flagged]
- ramon156 2y ago
  [flagged]
  - naikrovek 2y ago
    [flagged]
tromp 2y ago
It's interesting indeed that Turing's machines as he defined them can never halt: > he does not discuss the halting of his machines at all, and makes no provision for the computational processes undertaken by his machines ever to stop; in particular, he has no convention as in contemporary accounts of a halt state for the machines So instead of asking whether they halt, Turing asked whether they ever print a particular symbol. Of course one could call that symbol the halting symbol, and adopt the convention that printing the halting symbol amounts to halting. So while Turing did not name it the "Halting Problem" he proved an obviously equivalent result.
- deleted 2y ago
  [deleted]
- tinganho 2y ago
  Note, the origins are stated in Wikipedia: > Many papers and textbooks refer the definition and proof of undecidability of the halting problem to Turing's 1936 paper. However, this is not correct.[19][24] Turing did not use the terms "halt" or "halting" in any of his published works, including his 1936 paper.[25] A search of the academic literature from 1936 to 1958 showed that the first published material using the term “halting problem” was Rogers (1957). However, Rogers says he had a draft of Davis (1958) available to him,[19] and Martin Davis states in the introduction that "the expert will perhaps find some novelty in the arrangement and treatment of topics",[26] so the terminology must be attributed to Davis.[ https://en.wikipedia.org/wiki/Halting_problem#Origin_of_the_halting_problem https://en.wikipedia.org/wiki/Halting_problem#Origin_of_the_...
  - syrak 2y ago
    The paper in the OP discusses this claim in section 3, and mentions that Kleene came even before that: > We would note that Kleene seems, however, to have already had the self-referential argument earlier in his classic book from 1952, Introduction to Metamathematics They also bring up the "symbol-printing problem" present in Turing's 1936 paper, which is trivially equivalent to the halting problem with today's hindsight. That paper has a well nuanced take with a lot of interesting information.
- FartyMcFarter 2y ago
  I think Rice's theorem implies that proving the undecidability of the halting problem is equivalent to proving the undecidability of any other non-trivial semantic property of a program (*). So this discussion is basically just splitting hairs as you said. https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_redu... (*) > Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, "does the program terminate for all inputs?"), unlike a syntactic property (for instance, "does the program contain an if-then-else statement?"). A non-trivial property is one which is neither true for every program, nor false for every program.
  - indolering 2y ago
    I kinda hate that people dress up this analysis as a theorem. We have lots of formally verified programs that show useful work can be done here. And even if we can't prove most of it, high assurance methods are very useful for preventing fuckery. I can't mathematically prove any lock is unpickable. But I can use a lock advanced enough that the cost of picking it becomes absurd. Also, theoretical quantum computers can solve whether a problem halts 100% of the time. So Rice's Theorem is theoretically meaningless.
    - tsimionescu 2y ago
      > We have lots of formally verified programs that show useful work can be done here. Yes, by restricting things to a non-Turing Complete subset. > Also, theoretical quantum computers can solve whether a problem halts 100% of the time. That is absolutely not true. Quantum computers are proven to be entirely equivalent to classical computers in terms of what problems they can solve. The only difference is that they seem to show an exponential speed advantage for a certain very limited subset of problems, mostly related to quantum transforms.
      - lou1306 2y ago
        > Yes, by restricting things to a non-Turing Complete subset. No, not necessarily. There are procedures that _can_ verify properties against Turing-complete and even infinite-state systems. It's just that no _general_ (as in, sound and complete) procedure can exist.
- spiritbear14 2y ago
  This version makes more sense to me. When the halting problem was first explained to me in school the professor didn't get into what it actually meant in terms of computability, just that we couldn't tell if a program halted or not then we just moved on.
- chuckadams 2y ago
  I actually like the symbol phrasing, it's more general than halting. You can't prove that any arbitrary program that can be in state X will ever actually reach state X. Besides, I feel like https://xkcd.com/1266/ https://xkcd.com/1266/ is relevant :)
deleted 2y ago
[deleted]
lisper 2y ago
This is ridiculous academic click-bait. Here is a quote from Turing's 1936 paper: "If a computing machine never writes down more than a finite number of symbols of the first kind [i.e. 0 or 1], it will be called circular. Otherwise it is said to be circle-free." He then goes on to prove that "circularity" as he has defined it is undecidable. So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are equivalent is an elementary exercise. He also proves that "there can be no machine £ which, when supplied with the S.D of an arbitrary machine AV, will determine vhether AV ever prints a given symbol (0 say)." Which, again, is trivially equivalent to the question of whether or not the machine ever enters a particular privileged state. Saying that Turing's paper was not about the halting problem because it doesn't use the word "halt" is like saying that the EPR paper was not about entanglement because it doesn't use the word "entangled".
- tromp 2y ago
  > Showing that these questions are equivalent is an elementary exercise. Do you mean that there's a simple computable mapping f from TMs as Turing defined them to TMs which can halt such that machine m prints finitely many 0s/1s iff f(m) halts?
  - lisper 2y ago
    No. In fact, my guess is that you can prove there is no such function. But (and I confess I have not thought this all the way through so I might be wrong) while producing such a mapping would be sufficient to carry out the equivalence proof (if it were possible, which I suspect it is not) it is not necessary. All that is necessary (I think) is to show that if a machine is non-circular, then it is possible to produce an equivalent machine by using a halting state which is entered after the machine prints its final "symbol of the first kind". And that seems like it should not be hard, though I concede I may have overstated my case by calling it trivial. (You also have to prove the opposite, that a machine with a halting state can be converted into a Turing-style TM, but that really is obviously trivial.)
    - 2y ago
Shorel 2y ago
[flagged]
- deleted 2y ago
  [deleted]
PaulHoule 2y ago
My grad school mate Ron Maimon one day told me in a bar about the problem of computable numbers in a way that made him sound like a serious crackpot. I thought about it enough to conclude that the “real” numbers were “phony” numbers because unlike the integers or rationals most of them don’t have a name and can’t be referred to specifically. I found out later that Turing had introduced the computable numbers idea and that was the work he had really done as opposed to the modern formulation of the halting problem. As for Ron he really descended into conspiracy theory insanity and got kicked off Quora because he was saying the Boston bombing was an inside job. I still wish Steve Wolfram would grow some balls, take his constructivist program seriously, and reject the axiom of choice.
- anon291 2y ago
  I think it's one of the more unfortunate thing in mathematics that the real numbers are as popular as they are. I'm with your roommate. I don't believe they exist. I don't think every set of rational numbers has a least upper bound
  - auggierose 2y ago
    I don't believe that either. But every set of rational numbers bounded from above has a least upper bound in the reals.
    - anon291 2y ago
      That's my point. I don't believe they do. I don't believe the reals are well defined since no one can name them. In general, I lean towards mathematical constructivism: https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_mathematics) https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_... I agree that computable real numbers exist, even if they're intractable to compute.
      - auggierose 2y ago
        If only those things existed that have a name, the world would be a pretty small and boring place. Also, that would be a world entirely defined by humans, and that just doesn't make sense.
xaellison 2y ago
WE COME TO A NUANCED CONCLUSION. DOWNLOAD TO FIND OUT WHAT. world's best abstract
- deleted 2y ago
  [deleted]
jekude 2y ago
While it is an interesting quirk of history that we mainly think about computability hand-in-hand with the "halting" problem instead of Turing's symbol-printing, there are so many more interesting nuggets in the 1936 paper (like computational universality, the first ever programming bugs, etc). I do think the paper linked gets the nuances of attribution here correct. I wrote up a little guide to Turing's paper a while back [0] if anyone is interested in reading it but needs help like I did. [0] https://github.com/planetlambert/turing/blob/main/GUIDE.md https://github.com/planetlambert/turing/blob/main/GUIDE.md
pjungwir 2y ago
Oh this is very helpful! When I read Turing's paper some years ago, this really confused me. The best sense I could make was that "circle-free" means "halts". But in popular explanations, writers often equate "halts" with "gives a result" and "doesn't halt" with "has a bug", i.e. an infinite loop. And Turing seems to connote just the opposite. The point is to print a real number, so if the program stops printing digits, something went wrong. (I guess many numbers would end in 0s forever.) From today's paper: > a program is circular, when it produces only finitely many digits of the output digit sequence, and circle-free, when it has succeeded in giving us an infinite digit sequence for the output real number. But I could never really believe my interpretation. It was just the best I could come up with, as an amateur reading the paper alone for fun. Later I read Petzold's book, and I'm not sure that really solved the trouble for me either. I've only read a few pages so far, but I'm gathering it's not as simple as I wanted: "circle-free" is not merely equivalent to "halts" after all. I'm looking forward to seeing their more nuanced take. EDIT: Btw, this reminds me of the best riddle I've ever invented myself. Q: What do you call a fully autonomous self-driving car that can operate with as much understanding as a person? A: N Gheavat Znpuvar. (I didn't say it was a good riddle.)
- byteknight 2y ago
  Now we can add me to the list of confused. > ... when it has succeeded in giving us an infinite digit sequence for the output real number. How can it actually ever succeed then? Infinity never ends.
  - legacynl 2y ago
    I don't think the examples are meant as actual real world things, but rather abstractions to help reason about the problem. The most important thing about the halting problem, is that Turing gave an example of a computational problem that is unsolvable, thereby proofing that from all possible computational problems, some of them are be unsolvable.
fallingfrog 2y ago
Tangential and a bit hand-wavey but: I think you can use a Turing-like argument to argue against the existence of a finite set of moral rules that covers every situation too. The argument goes: suppose you have some set of rules. Now engineer a situation where, if the rules are followed, you cause something bad to happen. That’s similar to the step where turing says, “now create a program that asks if p halts, and if so runs an infinite loop”. Which means, no sacred text or set of commandments could possibly cover every situation.

81 points by vitplister 2y ago

kouru225 2y ago

[flagged]

ramon156 2y ago
[flagged]
- naikrovek 2y ago
  [flagged]

tromp 2y ago

It's interesting indeed that Turing's machines as he defined them can never halt: > he does not discuss the halting of his machines at all, and makes no provision for the computational processes undertaken by his machines ever to stop; in particular, he has no convention as in contemporary accounts of a halt state for the machines So instead of asking whether they halt, Turing asked whether they ever print a particular symbol. Of course one could call that symbol the halting symbol, and adopt the convention that printing the halting symbol amounts to halting. So while Turing did not name it the "Halting Problem" he proved an obviously equivalent result.

deleted 2y ago
[deleted]
tinganho 2y ago
Note, the origins are stated in Wikipedia: > Many papers and textbooks refer the definition and proof of undecidability of the halting problem to Turing's 1936 paper. However, this is not correct.[19][24] Turing did not use the terms "halt" or "halting" in any of his published works, including his 1936 paper.[25] A search of the academic literature from 1936 to 1958 showed that the first published material using the term “halting problem” was Rogers (1957). However, Rogers says he had a draft of Davis (1958) available to him,[19] and Martin Davis states in the introduction that "the expert will perhaps find some novelty in the arrangement and treatment of topics",[26] so the terminology must be attributed to Davis.[ https://en.wikipedia.org/wiki/Halting_problem#Origin_of_the_halting_problem https://en.wikipedia.org/wiki/Halting_problem#Origin_of_the_...
- syrak 2y ago
  The paper in the OP discusses this claim in section 3, and mentions that Kleene came even before that: > We would note that Kleene seems, however, to have already had the self-referential argument earlier in his classic book from 1952, Introduction to Metamathematics They also bring up the "symbol-printing problem" present in Turing's 1936 paper, which is trivially equivalent to the halting problem with today's hindsight. That paper has a well nuanced take with a lot of interesting information.
FartyMcFarter 2y ago
I think Rice's theorem implies that proving the undecidability of the halting problem is equivalent to proving the undecidability of any other non-trivial semantic property of a program (*). So this discussion is basically just splitting hairs as you said. https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_reduction_from_the_halting_problem https://en.wikipedia.org/wiki/Rice%27s_theorem#Proof_by_redu... (*) > Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, "does the program terminate for all inputs?"), unlike a syntactic property (for instance, "does the program contain an if-then-else statement?"). A non-trivial property is one which is neither true for every program, nor false for every program.
- indolering 2y ago
  I kinda hate that people dress up this analysis as a theorem. We have lots of formally verified programs that show useful work can be done here. And even if we can't prove most of it, high assurance methods are very useful for preventing fuckery. I can't mathematically prove any lock is unpickable. But I can use a lock advanced enough that the cost of picking it becomes absurd. Also, theoretical quantum computers can solve whether a problem halts 100% of the time. So Rice's Theorem is theoretically meaningless.
  - tsimionescu 2y ago
    > We have lots of formally verified programs that show useful work can be done here. Yes, by restricting things to a non-Turing Complete subset. > Also, theoretical quantum computers can solve whether a problem halts 100% of the time. That is absolutely not true. Quantum computers are proven to be entirely equivalent to classical computers in terms of what problems they can solve. The only difference is that they seem to show an exponential speed advantage for a certain very limited subset of problems, mostly related to quantum transforms.
    - lou1306 2y ago
      > Yes, by restricting things to a non-Turing Complete subset. No, not necessarily. There are procedures that _can_ verify properties against Turing-complete and even infinite-state systems. It's just that no _general_ (as in, sound and complete) procedure can exist.
spiritbear14 2y ago
This version makes more sense to me. When the halting problem was first explained to me in school the professor didn't get into what it actually meant in terms of computability, just that we couldn't tell if a program halted or not then we just moved on.
chuckadams 2y ago
I actually like the symbol phrasing, it's more general than halting. You can't prove that any arbitrary program that can be in state X will ever actually reach state X. Besides, I feel like https://xkcd.com/1266/ https://xkcd.com/1266/ is relevant :)

deleted 2y ago

[deleted]

lisper 2y ago

This is ridiculous academic click-bait. Here is a quote from Turing's 1936 paper: "If a computing machine never writes down more than a finite number of symbols of the first kind [i.e. 0 or 1], it will be called circular. Otherwise it is said to be circle-free." He then goes on to prove that "circularity" as he has defined it is undecidable. So no, he never defines "halting", he just talks about whether or not a machine ever prints a finite number of 1's and 0's. Showing that these questions are equivalent is an elementary exercise. He also proves that "there can be no machine £ which, when supplied with the S.D of an arbitrary machine AV, will determine vhether AV ever prints a given symbol (0 say)." Which, again, is trivially equivalent to the question of whether or not the machine ever enters a particular privileged state. Saying that Turing's paper was not about the halting problem because it doesn't use the word "halt" is like saying that the EPR paper was not about entanglement because it doesn't use the word "entangled".

tromp 2y ago
> Showing that these questions are equivalent is an elementary exercise. Do you mean that there's a simple computable mapping f from TMs as Turing defined them to TMs which can halt such that machine m prints finitely many 0s/1s iff f(m) halts?
- lisper 2y ago
  No. In fact, my guess is that you can prove there is no such function. But (and I confess I have not thought this all the way through so I might be wrong) while producing such a mapping would be sufficient to carry out the equivalence proof (if it were possible, which I suspect it is not) it is not necessary. All that is necessary (I think) is to show that if a machine is non-circular, then it is possible to produce an equivalent machine by using a halting state which is entered after the machine prints its final "symbol of the first kind". And that seems like it should not be hard, though I concede I may have overstated my case by calling it trivial. (You also have to prove the opposite, that a machine with a halting state can be converted into a Turing-style TM, but that really is obviously trivial.)
  - 2y ago

Shorel 2y ago

[flagged]

deleted 2y ago
[deleted]

PaulHoule 2y ago

My grad school mate Ron Maimon one day told me in a bar about the problem of computable numbers in a way that made him sound like a serious crackpot. I thought about it enough to conclude that the “real” numbers were “phony” numbers because unlike the integers or rationals most of them don’t have a name and can’t be referred to specifically. I found out later that Turing had introduced the computable numbers idea and that was the work he had really done as opposed to the modern formulation of the halting problem. As for Ron he really descended into conspiracy theory insanity and got kicked off Quora because he was saying the Boston bombing was an inside job. I still wish Steve Wolfram would grow some balls, take his constructivist program seriously, and reject the axiom of choice.

anon291 2y ago
I think it's one of the more unfortunate thing in mathematics that the real numbers are as popular as they are. I'm with your roommate. I don't believe they exist. I don't think every set of rational numbers has a least upper bound
- auggierose 2y ago
  I don't believe that either. But every set of rational numbers bounded from above has a least upper bound in the reals.
  - anon291 2y ago
    That's my point. I don't believe they do. I don't believe the reals are well defined since no one can name them. In general, I lean towards mathematical constructivism: https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_mathematics) https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_... I agree that computable real numbers exist, even if they're intractable to compute.
    - auggierose 2y ago
      If only those things existed that have a name, the world would be a pretty small and boring place. Also, that would be a world entirely defined by humans, and that just doesn't make sense.

xaellison 2y ago

WE COME TO A NUANCED CONCLUSION. DOWNLOAD TO FIND OUT WHAT. world's best abstract

deleted 2y ago
[deleted]

jekude 2y ago

While it is an interesting quirk of history that we mainly think about computability hand-in-hand with the "halting" problem instead of Turing's symbol-printing, there are so many more interesting nuggets in the 1936 paper (like computational universality, the first ever programming bugs, etc). I do think the paper linked gets the nuances of attribution here correct. I wrote up a little guide to Turing's paper a while back [0] if anyone is interested in reading it but needs help like I did. [0] https://github.com/planetlambert/turing/blob/main/GUIDE.md https://github.com/planetlambert/turing/blob/main/GUIDE.md

pjungwir 2y ago

Oh this is very helpful! When I read Turing's paper some years ago, this really confused me. The best sense I could make was that "circle-free" means "halts". But in popular explanations, writers often equate "halts" with "gives a result" and "doesn't halt" with "has a bug", i.e. an infinite loop. And Turing seems to connote just the opposite. The point is to print a real number, so if the program stops printing digits, something went wrong. (I guess many numbers would end in 0s forever.) From today's paper: > a program is circular, when it produces only finitely many digits of the output digit sequence, and circle-free, when it has succeeded in giving us an infinite digit sequence for the output real number. But I could never really believe my interpretation. It was just the best I could come up with, as an amateur reading the paper alone for fun. Later I read Petzold's book, and I'm not sure that really solved the trouble for me either. I've only read a few pages so far, but I'm gathering it's not as simple as I wanted: "circle-free" is not merely equivalent to "halts" after all. I'm looking forward to seeing their more nuanced take. EDIT: Btw, this reminds me of the best riddle I've ever invented myself. Q: What do you call a fully autonomous self-driving car that can operate with as much understanding as a person? A: N Gheavat Znpuvar. (I didn't say it was a good riddle.)

byteknight 2y ago
Now we can add me to the list of confused. > ... when it has succeeded in giving us an infinite digit sequence for the output real number. How can it actually ever succeed then? Infinity never ends.
- legacynl 2y ago
  I don't think the examples are meant as actual real world things, but rather abstractions to help reason about the problem. The most important thing about the halting problem, is that Turing gave an example of a computational problem that is unsolvable, thereby proofing that from all possible computational problems, some of them are be unsolvable.

fallingfrog 2y ago

Tangential and a bit hand-wavey but: I think you can use a Turing-like argument to argue against the existence of a finite set of moral rules that covers every situation too. The argument goes: suppose you have some set of rules. Now engineer a situation where, if the rules are followed, you cause something bad to happen. That’s similar to the step where turing says, “now create a program that asks if p halts, and if so runs an infinite loop”. Which means, no sacred text or set of commandments could possibly cover every situation.