<p><em>Is it due to Sipser? Or Penrose?</em></p>

<p>Sorry, that made me laugh out loud.  Penrose?</p>

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

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

<p>This 1963 paper by Evey (<a href="https://www.computer.org/csdl/proceedings/afips/1963/5063/00/50630215.pdf" rel="noreferrer">https://www.computer.org/csdl/proceedings/afips/1963/5063/00/50630215.pdf</a> ) 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.</p>

CC BY-SA 3.0
2016-09-14T15:38:53.493Z
Yes, I can see the connection to Frege.  But who or what ever recast the Turing machine in terms of recognizing whether a given string belongs to a given language?
Amittai Aviram
CC BY-SA 3.0
2016-09-14T15:58:23.170Z
Seriously, why on earth would it be Penrose?
Sasho Nikolov
CC BY-SA 3.0
2016-09-15T10:09:35.313Z
Chomsky was parsing *natural* written languages, such as English or Russian.
reinierpost
CC BY-SA 3.0
2016-09-19T11:18:17.527Z
@reinierpost: Chomsky was parsing artificial languages, in a way very relevant for computer science. His *motivation* was that he wanted to use them to model natural languages.
Peter Shor 
CC BY-SA 3.0
2016-09-19T12:39:37.170Z
Chomsky wanted to describe written natural language. He wasn't interested in artificial languages. The Chomsky hierarchy was invented as a way to classify the descriptiive power of formalisms for describing natural languages. It was John Backus who applied the ideas to a programming language. The idea of viewing streams of events as languages to be recognized existed before Chomsky, see e.g. Kleene's paper introducing regular expressions and finite automata, but Kleene didn't use the word language as far as I  am aware.
reinierpost
CC BY-SA 3.0
2016-09-24T12:20:00.073Z
@reinierpost: From Chomsky's paper *"With this condition in mind, we can easily construct many non-finite state languages. For example, the languages L$_1$,  L$_2$, L$_3$ described in (12) are not describable by any finite-state grammar"*. Are you saying that L$_1$, L$_2$, L$_3$
are natural languages? Are you saying that Chomsky wasn't parsing them? He wasn't interested in computer languages, but that's not what I meant by *"artificial languages".* Many of the examples in his paper are indeed from English, but not all of them.
Peter Shor 
CC BY-SA 3.0
2016-09-24T20:37:43.420Z
Of course artificial languages will arise in discussing this theory. My point is that describing artificial languages wasn't his goal.
reinierpost
CC BY-SA 3.0
2016-09-14T14:06:46.687Z
2016-09-15T14:44:51.023Z
2016-09-15T14:44:51.023Z
Jeffrey Shallit
<p>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 <em>The Complexity of Theorem-Proving Procedures</em>, which proved the Cook-Levin theorem, we find</p>

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

<p>This is a form of the <em>recognizer</em> 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. </p>

<p>The difference between <em>languages</em> and <em>functions</em> you ask about in (2) is implicit in Cook's paper. It harks back to logic, and the relationship between <em>recursively enumerable sets</em> and <em>computable functions</em>, 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 <a href="https://en.wikipedia.org/wiki/Chomsky_hierarchy" rel="nofollow">Chomsky hierarchy</a> of languages is very influential in computer science, and certainly was known to computer scientists. </p>

CC BY-SA 3.0
2016-09-16T22:27:38.417Z
No, it is certainly not due to Cook. There are papers from the mid 1960's that talk about Turing machines recognizing languages, for example, from the Princeton conference of 1967.
Jeffrey Shallit
CC BY-SA 3.0
2016-09-16T23:53:03.863Z
@Jeffrey: Okay, I've modified my answer.
Peter Shor 
CC BY-SA 3.0
2016-09-19T13:49:21.137Z
Currently I think the idea really bloomed in the mid-1960's and then was solidified by Hopcroft and Ullman's 1969 book "Formal Languages and Their Relation to Automata Theory", a predecessor to their 1979 textbook.
Jeffrey Shallit
CC BY-SA 3.0
2016-09-16T12:18:21.067Z
2016-09-16T23:53:01.627Z
2016-09-16T23:53:01.627Z
Peter Shor 
<p>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:</p>

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

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

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

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

<p>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:</p>

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

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

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

<p>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:</p>

<ol>
<li>All computation stops at some point. This leaves a finite set of F squares printed, and is isomorphic to the modern notion of "halting".</li>
<li>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.</li>
</ol>

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

<p>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 <span class="math-container">$\Delta_{3}$</span> functions, rather than the halting related <span class="math-container">$\Delta_{2}$</span>. Phrased as a decision problem the two classes (Satisfactory and Circular) are : <span class="math-container">$\Pi_{2}$</span> versus <span class="math-container">$\Sigma_2$</span>. (The familiar classes are of course <span class="math-container">$\Pi_{1}$</span> versus <span class="math-container">$\Sigma_{1}$</span> (= partial recursive class.))</p>

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

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

CC BY-SA 4.0
2019-01-21T16:00:38.340Z
2019-01-21T16:00:38.340Z
Roy Simpson
<p>Turing's original 1936 description of his <em>a</em>-machine differs in several respects from the Turing machine I studied at university, leading me to questions:</p>

<ol>
<li><p>The Turing machine I learned about was essentially a recognizer: it would either accept or reject input having specified characteristics.  It has an <em>accept</em> or <em>halt</em> final state.  By contrast, Turing describes a computing machine proper--his model computations involve <em>producing</em> and <em>outputting</em> numbers--without any particular <em>halt</em> state--although, for the proof that the <em>Entscheidungsproblem</em> has no solution, he does propose a machine D that would mark as "s" or "u" some other machine based on whether it is <em>circular</em> ("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?</p></li>
<li><p>The version of the Turing machine I got--e.g., from Sipser--required a definition of <em>language</em> as a "set of strings," where a Turing machine would recognize a given input string as belonging or not to some language <em>L</em>.  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?</p></li>
<li><p>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 <em>circular</em>."  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 <em>circular</em>.  Moreover, Turing never explains what is <em>circular</em> 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.</p></li>
</ol>

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

<p>Thanks!</p>

CC BY-SA 3.0
2016-09-14T06:59:23.350Z
"... Is he just leaving out an argument that the reader is supposed to infer? ..." I think he explains in detail what *circular* (and *circle-free*) means and why it is used: "*...A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term "circular" will be explained in §8* (Application of the diagonal process) ..."
Marzio De Biasi
CC BY-SA 3.0
2016-09-14T15:41:36.587Z
I already acknowledged Turing's definition in my posting.  This still does not explain at all (a) why this condition is called "circular" or (b) the relation between *this* concept of circularity and the concept, more familiar to students today, of a machine that never halts--which, at least on the surface, sounds like the *opposite* of Turing's circular machine.  A halting state is by definition a state "from which there is no possible move."
Amittai Aviram
<automata-theory><turing-machines><machine-models>
Where does the modern canonical version of the Turing machine come from?
Amittai Aviram
# Where does the modern canonical version of the Turing machine come from?

(Asked by: username_0 on 2016-09-14)

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!

**Tags:** automata-theory, turing-machines, machine-models
> **Comments:**
> **username_1**: "... Is he just leaving out an argument that the reader is supposed to infer? ..." I think he explains in detail what *circular* (and *circle-free*) means and why it is used: "*...A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term "circular" will be explained in §8* (Application of the diagonal process) ..."  
> **username_0**: I already acknowledged Turing's definition in my posting.  This still does not explain at all (a) why this condition is called "circular" or (b) the relation between *this* concept of circularity and the concept, more familiar to students today, of a machine that never halts--which, at least on the surface, sounds like the *opposite* of Turing's circular machine.  A halting state is by definition a state "from which there is no possible move."  

---

## 3 answers

### Answer by username_2 on 2016-09-14. Score: 8

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

> **Comments:**
> **username_0**: Yes, I can see the connection to Frege.  But who or what ever recast the Turing machine in terms of recognizing whether a given string belongs to a given language?  
> **username_3**: Seriously, why on earth would it be Penrose?  
> **username_4**: Chomsky was parsing *natural* written languages, such as English or Russian.  
> **username_5**: @reinierpost: Chomsky was parsing artificial languages, in a way very relevant for computer science. His *motivation* was that he wanted to use them to model natural languages.  
> **username_4**: Chomsky wanted to describe written natural language. He wasn't interested in artificial languages. The Chomsky hierarchy was invented as a way to classify the descriptiive power of formalisms for describing natural languages. It was John Backus who applied the ideas to a programming language. The idea of viewing streams of events as languages to be recognized existed before Chomsky, see e.g. Kleene's paper introducing regular expressions and finite automata, but Kleene didn't use the word language as far as I  am aware.  
> **username_5**: @reinierpost: From Chomsky's paper *"With this condition in mind, we can easily construct many non-finite state languages. For example, the languages L$_1$,  L$_2$, L$_3$ described in (12) are not describable by any finite-state grammar"*. Are you saying that L$_1$, L$_2$, L$_3$ are natural languages? Are you saying that Chomsky wasn't parsing them? He wasn't interested in computer languages, but that's not what I meant by *"artificial languages".* Many of the examples in his paper are indeed from English, but not all of them.  
> **username_4**: Of course artificial languages will arise in discussing this theory. My point is that describing artificial languages wasn't his goal.  

---

### Answer by username_5 on 2016-09-16. Score: 5

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](https://en.wikipedia.org/wiki/Chomsky_hierarchy) of languages is very influential in computer science, and certainly was known to computer scientists.

> **Comments:**
> **username_2**: No, it is certainly not due to Cook. There are papers from the mid 1960's that talk about Turing machines recognizing languages, for example, from the Princeton conference of 1967.  
> **username_5**: @Jeffrey: Okay, I've modified my answer.  
> **username_2**: Currently I think the idea really bloomed in the mid-1960's and then was solidified by Hopcroft and Ullman's 1969 book "Formal Languages and Their Relation to Automata Theory", a predecessor to their 1979 textbook.  

---

### Answer by username_6 on 2019-01-21. Score: 4

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.


---

