Did Turing prove the undecidability of the halting problem?

by vitplister • 2 years ago

81 105 2 years ago

tromp4• 2 years 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.

tinganho• 2 years 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_...

syrak2• 2 years 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.

FartyMcFarter7• 2 years 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_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• 2 years 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.

User235• 2 years ago

It’s worth noting that the undecidability of the halting problem doesn’t prevent computing scientists from proving that a program halts or has some other nontrivial property.

spiritbear14• 2 years 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.

chuckadams2• 2 years 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/ is relevant :)

lisper7• 2 years 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".

tromp4• 2 years 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?

lisper7• 2 years 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.)

less_less• 2 years ago

I think you'd want the reverse, which is indeed elementary: if f halts then you get a circle-free TM, but if f does not halt then you get a non-circle-free TM. This can be done by

  f(); while(1) output_digit(0);

or any number of other simple constructions. This is because a circle-free TM always reaches a certain pre-defined event (output_digit), much like a halting TM. But a non-circle-free TM might forever fail to make progress, in a way that you can't necessarily tell if it's stuck or will eventually output another digit, much like a non-halting TM.

Edited to add: also Turing proved that the symbol-printing problem is undecidable, as the authors of this paper describe: will a Turing machine ever print a certain symbol? If you name the symbol in question "HALT" then this is almost identical to the halting problem, and easily reducible in either direction.

Sharlin• 2 years ago

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.

I think it's subtler than that. Circular programs in Turing's language are those that return to some exact earlier state and thus go into an infinite loop. So circular programs by definition do not halt. But circle-free programs can either halt or not halt!

lisper7• 2 years ago

Circular programs in Turing's language are those that return to some exact earlier state

No, they aren't. They are programs that print a finite number of "symbols of the first kind" i.e. 0s and 1s. They can print an infinite number of other symbols.

You might want to check out this branch of the discussion:

https://news.ycombinator.com/item?id=40855382

PaulHoule• 2 years 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.

anon29111• 2 years 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

auggierose5• 2 years ago

I don't believe that either. But every set of rational numbers bounded from above has a least upper bound in the reals.

kbelder• 2 years ago

I found his Physics Stack Exchange answers to be immensely valuable. Although, I did have to read everything he wrote with a little bit of a critical eye, due to some of the rants he went on.

I'm glad to see he bought into the abiotic generation of oil; it's my favorite fringe theory I just can't shake.

xaellison• 2 years ago

WE COME TO A NUANCED CONCLUSION. DOWNLOAD TO FIND OUT WHAT.

world's best abstract

jekude• 2 years 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

pjungwir• 2 years 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• 2 years 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• 2 years 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• 2 years 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.

Did Turing prove the undecidability of the halting problem?

Related Stories