Did Turing prove the undecidability of the halting problem?

It&#x27;s interesting indeed that Turing&#x27;s machines as he defined them can never halt:<p>&gt; 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<p>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 &quot;Halting Problem&quot; he proved an obviously equivalent result.

While it is an interesting quirk of history that we mainly think about computability hand-in-hand with the &quot;halting&quot; problem instead of Turing&#x27;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.<p>I wrote up a little guide to Turing&#x27;s paper a while back [0] if anyone is interested in reading it but needs help like I did.<p>[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;planetlambert&#x2F;turing&#x2F;blob&#x2F;main&#x2F;GUIDE.md">https:&#x2F;&#x2F;github.com&#x2F;planetlambert&#x2F;turing&#x2F;blob&#x2F;main&#x2F;GUIDE.md</a>

This is ridiculous academic click-bait. Here is a quote from Turing&#x27;s 1936 paper:<p>&quot;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.&quot;<p>He then goes on to prove that &quot;circularity&quot; as he has defined it is undecidable.<p>So no, he never defines &quot;halting&quot;, he just talks about whether or not a machine ever prints a finite number of 1&#x27;s and 0&#x27;s. Showing that these questions are equivalent is an elementary exercise.<p>He also proves that &quot;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).&quot; Which, again, is trivially equivalent to the question of whether or not the machine ever enters a particular privileged state.<p>Saying that Turing&#x27;s paper was not about the halting problem because it doesn&#x27;t use the word &quot;halt&quot; is like saying that the EPR paper was not about entanglement because it doesn&#x27;t use the word &quot;entangled&quot;.

Oh this is very helpful!<p>When I read Turing&#x27;s paper some years ago, this really confused me. The best sense I could make was that &quot;circle-free&quot; means &quot;halts&quot;. But in popular explanations, writers often equate &quot;halts&quot; with &quot;gives a result&quot; and &quot;doesn&#x27;t halt&quot; with &quot;has a bug&quot;, 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&#x27;s paper:<p>&gt; 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.<p>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&#x27;s book, and I&#x27;m not sure that really solved the trouble for me either.<p>I&#x27;ve only read a few pages so far, but I&#x27;m gathering it&#x27;s not as simple as I wanted: &quot;circle-free&quot; is not merely equivalent to &quot;halts&quot; after all. I&#x27;m looking forward to seeing their more nuanced take.<p>EDIT: Btw, this reminds me of the best riddle I&#x27;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&#x27;t say it was a <i>good</i> riddle.)

Tangential and a bit hand-wavey but:<p>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”.<p>Which means, no sacred text or set of commandments could possibly cover <i>every</i> situation.

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.<p>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.<p>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.

WE COME TO A NUANCED CONCLUSION. DOWNLOAD TO FIND OUT WHAT.<p>world&#x27;s best abstract