The origins of the halting problem





Publicado en

Actas de las XXI Jornadas de Programación y Lenguajes (PROLE 2022)

Licencia Creative Commons


The halting problem is a prominent example of undecidable problem and its formulation and undecidability proof is usually attributed to Turing's 1936 landmark paper. Copeland noticed in 2004, though, that it was so named and, apparently, first stated in a 1958 book by Martin Davis. We provide additional arguments partially supporting this claim as follows: (i) with a focus on computable (real) numbers with infinitely many digits (e.g., +A8A), in his paper Turing was not concerned with halting machines+ADs (ii) the two decision problems considered by Turing concern the ability of his machines to produce specific kinds of outputs, rather than reaching a halting state, something which was missing from Turing's notion of computation+ADs and (iii) from 1936 to 1958, when considering the literature of the field no paper refers to any +IBw-halting problem+IB0 of Turing Machines until Davis' book. However, there were important preliminary contributions by (iv) Church, for whom termination was part of his notion of computation (for the +A7s--calculus), and (v) Kleene, who essentially formulated, in his 1952 book, what we know as the halting problem now.


Acerca de Lucas, Salvador

Palabras clave

Halting Problem, Printing Problem, Program Termination
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX