Tag Archives: Turing

Did Turing prove the undecidability of the halting problem?

Posted on by
1

Joel David Hamkins and Theodor Nenu, “Did Turing prove the undecidability of the halting problem?”, 18 pages, 2024, Mathematics arXiv:2407.00680.

Abstract. We discuss the accuracy of the attribution commonly given to Turing (1936) for the computable undecidability of the halting problem, eventually coming to a nuanced conclusion.

The halting problem is the decision problem of determining whether a given computer program halts on a given input, a problem famously known to be computably undecidable. In the computability theory literature, one quite commonly finds attribution for this result given to Alan Turing (1936), and we should like to consider the extent to which these attributions are accurate. After all, the term halting problem, the modern formulation of the problem, as well as the common self-referential proof of its undecidability, are all—strictly speaking—absent from Turing’s work. However, Turing does introduce the concept of an undecidable decision problem, proving that what he calls the circle-free problem is undecidable and subsequently also that what we call the symbol-printing problem, to decide if a given program will ever print a given symbol, is undecidable. This latter problem is easily seen to be computably equivalent to the halting problem and can arguably serve in diverse contexts and applications in place of the halting problem—they are easily translated to one another. Furthermore, Turing laid down an extensive framework of ideas sufficient for the contemporary analysis of the halting problem, including: the definition of Turing machines; the labeling of programs by numbers in a way that enables programs to be enumerated and also for them to be given as input to other programs; the existence of a universal computer; the undecidability of several problems that, like the halting problem, take other programs as input, including the circle-free problem, the symbol-printing problem, and the infinite-symbol-printing problem, as well as the Hilbert-Ackermann Entscheidungsproblem. In light of these facts, and considering some general cultural observations, by which mathematical attributions are often made not strictly for the exact content of original work, but also generously in many cases for the further aggregative insights to which those ideas directly gave rise, ultimately we do not find it unreasonable to offer qualified attribution to Turing for the undecidability of the halting problem. That said, we also find it incorrect to suggest that one will find a discussion of the halting problem or a proof of its undecidability in Turing (1936).

Read the full paper at the mathematics arxiv:2407.00680. (pdf download available)

Bibliography

The hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility, Florida, 2012

Posted on by
1

This is a talk at the Alan Turing centenary conference at Florida Atlantic University, January 13-15, 2012, sponsored by MAMLS, and part of the 2012 Alan Turing Year of events in celebration of the one hundredth year of the birth of Alan Turing.

This talk will be about a recent generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In our computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, rather than on the difficulty of computing the relations themselves.  In particular, the theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.  This is joint work with Sam Coskey and Russell Miller.

Article | Sam’s post on this topic | Slides