Halting problem
Origin of the halting problem

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. Turing did not use the terms "halt" or "halting" in any of his published works, including his 1936 paper. 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, and Martin Davis states in the introduction that "the expert will perhaps find some novelty in the arrangement and treatment of topics", so the terminology must be attributed to Davis. Davis stated in a letter that he had been referring to the halting problem since 1952. The usage in Davis's book is as follows:

" we wish to determine whether or not Z, if placed in a given initial state, will eventually halt. We call this problem the halting problem for Z.

Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable.

A related problem is the printing problem for a simple Turing machine Z with respect to a symbol S ".

A possible precursor to Davis's formulation is Kleene's 1952 statement, which differs only in wording:

there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops.

The halting problem is Turing equivalent to both Davis's printing problem ("does a Turing machine starting from a given state ever print a given symbol?") and to the printing problem considered in Turing's 1936 paper ("does a Turing machine starting from a blank tape ever print a given symbol?"). However, Turing equivalence is rather loose and does not mean that the two problems are the same. There are machines which print but do not halt, and halt but not print. The printing and halting problems address different issues and exhibit important conceptual and technical differences. Thus, Davis was simply being modest when he said:

It might also be mentioned that the unsolvability of essentially these problems was first obtained by Turing.
oulipo:avoid_letter[o]