Where does the modern canonical version of the Turing machine come from?

Question

Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions:

1. The Turing machine I learned about was essentially a recognizer: it would either accept or reject input having specified characteristics. It has an accept or halt final state. By contrast, Turing describes a computing machine proper--his model computations involve producing and outputting numbers--without any particular halt state--although, for the proof that the Entscheidungsproblem has no solution, he does propose a machine D that would mark as "s" or "u" some other machine based on whether it is circular ("u"). Where does the recognizer view of the Turing machine come from? Is it the result of later theorists focusing in on the imaginary machine D in Section 8 of Turing's paper?

2. The version of the Turing machine I got--e.g., from Sipser--required a definition of language as a "set of strings," where a Turing machine would recognize a given input string as belonging or not to some language L. Where does this idea come from? Turing's model of computation makes no reference to this concept of "language." Is it due to Sipser? Or Penrose?

3. Turing defines "circular" in a way that seems surprising and counterintuitive today: "If a computing machine never writes down more than a finite number of symbols of the first kind [i.e., symbols from {0, 1}], it will be called circular." Suppose you want the machine to compute a + b, where a and b are integers. This sounds as if a machine that halts when finished computing a number with a finite representation is circular. Moreover, Turing never explains what is circular in the common sense of the word about such a machine. Is he just leaving out an argument that the reader is supposed to infer? Presumably, the argument would go thus: if we assume (but why?) that the machine should compute a number whose representation is infinite, then, if the machine halts, this can only result from a circularity in the state diagram--either one state leads to itself, without any motion or change of written symbol, or the states follow in a circular sequence with an equivalent result. That seems to me to presuppose a lot--for instance, that the circularity does not result in any motion beyond the squares already written and that the written symbols remain the same as before.

Was there published work leading up to Turing's 1936 paper already introducing the concept of circularity, so that he could merely allude to it?

Thanks!

Answer 1

Is it due to Sipser? Or Penrose?

Sorry, that made me laugh out loud. Penrose?

Today's notion of formal language (a language is a set of words or strings) can be traced at least as far back as Frege in the late 1800's and Thue in the early 1900's. Chomsky's 1956 paper was very influential, and definitely uses the term "language" for a set of strings.

There is also the 1961 paper of Bar-Hillel, Perles, and Shamir. I would check that.

This 1963 paper by Evey (https://www.computer.org/csdl/proceedings/afips/1963/5063/00/50630215.pdf ) uses the term "language" in the modern sense in relation to machines. Perhaps earlier explicit references can be found in the work of Emil Post.

Answer 2

Your question (1) is essentially the difference between Turing machines that recognize languages and Turing machines that compute functions. This difference is essential for proving theorems about complexity classes like NP. And in fact, if we look at Cook's 1971 paper The Complexity of Theorem-Proving Procedures, which proved the Cook-Levin theorem, we find

In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles in [1]. A query machine is a multitape Turing machine with a distinguished tape called the query tape, and three distinguished states called the query state, yes state, and no state, respectively.

This is a form of the recognizer Turing machine that you ask about in (1). So I would say the view of Turing machines as recognizing languages is a product of their use in complexity theory, where languages rather than functions are the primary object of study.

The difference between languages and functions you ask about in (2) is implicit in Cook's paper. It harks back to logic, and the relationship between recursively enumerable sets and computable functions, which was studied in the 1930s. As Jeffrey Shallit's answer says, Chomsky's 1956 paper also defines languages as a set of strings. While Chomsky's paper was motivated by linguistics, the Chomsky hierarchy of languages is very influential in computer science, and certainly was known to computer scientists.

Answer 3

I view this question as one in the history of Turing machine theory, which indeed has had more changes than are evident from contemporary textbooks. The Turing model of 1936 was remarkably different from the later more accepted formulations. In more detail in terms of your questions:

(1),(2) The modern formulation in terms of Recogniser, and Languages emerges from the 1960s models of automata (as simpler subtypes of Turing Machines). These automata models were designed to help understand the kind of languages (Context Free, etc) being introduced into the practice and were isomorphic to the language structures introduced by Chomsky. Eventually textbooks often used the Recogniser - Languages paradigm for describing full Turing Machines themselves. Part of the move towards that may well be the early work on NP Completeness referred to by Peter Shor.

For example "non-determinism" was introduced as an automata concept in 1960, and later, once some theorems had been proven about non-deterministic automata, it became clear that some complexity problems were significant. All this despite the fact that Turing had already introduced the idea as his c-machines in 1936 ("c-" here meant "choice" machine as opposed to "a-" which meant "automatic" machine.) I have no evidence that Turing ever investigated this machine type any further, or that he used the term "non-deterministic" in this context.

Of importance to this story is that there was another important stage between Turing 1936 and the 1960s which was the formalisations and theory from Emil Post (with the 1950s textbooks of Kleene and Davis). I shall return to that after making remarks about Turing 1936 wrt questions (1) and (3).

Turing 1936 was really about trying to solve a very universal problem in mathematical logic, and the machine models constructed were all an aid in that direction. The construction ideas were largely original, although there is debate as to what prior machine models he was actually familiar with.

The title of the paper began "On Computable Numbers" and this set the theme for all the constructions. Since computable numbers were real numbers this required the a-machine to compute the entire number (in principle). Hence for the sake of generality the machine needed to compute forever to be satisfactory. As his diagonalization proof showed, some machines would get stuck in a loop and not print out an infinite sequence - these were circular. Now a modern reader needs to be aware that the a-machine tape needs to have room to do:

(a) Printing of permanent output - Turing's F (for Fixed) squares;

(b) Scrap work, calculational squares (the memory) - Turing's E (for Erasable) squares.

In his examples the tape was set thus: F-E-F-E-F- … alternating between the two types.

Thus his satisfactory machines were required to print indefinitely (and sequentially) on the F squares. You will see that there are two alternatives to this:

1. All computation stops at some point. This leaves a finite set of F squares printed, and is isomorphic to the modern notion of "halting".
2. The computation stops printing F squares at some point, but continues printing on E squares (perhaps erasing some). This machine does not stop, but is not satisfactory and is clearly circular. This was the machine behaviour of the diagonalization machine constructed in his proof.

Tacitly both types (1) and (2) are in the "circular" class, although only non-stopping machines could be considered in the normal interpretation of that term.

Remarkably what this means is that logically Turing's 1936 a-machine behaved differently from the modern machines, and his theorem was not logically equivalent to the halting theorem. Because of this possibility of things happening infinitely, this means that he proved that his machines could not compute $\Delta_{3}$ functions, rather than the halting related $\Delta_{2}$. Phrased as a decision problem the two classes (Satisfactory and Circular) are : $\Pi_{2}$ versus $\Sigma_2$. (The familiar classes are of course $\Pi_{1}$ versus $\Sigma_{1}$ (= partial recursive class.))

Now Post in 1936 had also produced a simple machine model, and unlike Turing continued to develop the theory (of recursive functions, machines and undecidability) into the 1940s. In his first paper proving the first undecidability result in mathematics (in 1947) he needed to precisely describe what a machine consisted of. This introduced the more familiar notion that the machine must stop before producing any result whatsoever. Post also critiqued Turing 1936 for adding an extra infinite process, and apparently Turing wrote a reply, but it was never sent.

Post 1947 was the definitive form of a machine (with no infinite processes) with only one omission - no Halting theorem! This was proven by Davis and Kleene independently in the 1950s and presented in their first books, along with Post's 1947 model now called the "Turing Machine" despite having several differences and simplifications.