Turing machines, first described byAlan Turing in Turing 1936–7, are simple abstract computational devicesintended to help investigate the extent and limitations of what can becomputed. Turing’s ‘automatic machines’, as hetermed them in 1936, were specifically devised for the computation ofreal numbers. They were first named ‘Turing machines’ byAlonzo Church in a review of Turing’s paper (Church 1937).Today, they are considered to be one of the foundational models ofcomputability and (theoretical) computer science.^[1]

• 1. Definitions of the Turing Machine
  • 1.1 Turing’s Definition
  • 1.2 Post’s Definition
  • 1.3 The Definition Formalized
  • 1.4 Describing the Behavior of a Turing Machine
• 2. Computing with Turing Machines
  • 2.1 Some (Simple) Examples
  • 2.2 Computable Numbers and Problems
  • 2.3 Turing’s Universal Machine
    • 2.3.1 Interchangeability of program and behavior: a notation
    • 2.3.2 Interchangeability of program and behavior: a basic set of functions
  • 2.4 The Halting Problem and the Entscheidungsproblem
    • 2.4.1 Direct and indirect proofs of uncomputable decision problems
    • 2.4.2 Turing’s basic problem CIRC?, PRINT? and the Entscheidungsproblem
    • 2.4.3 The halting problem
  • 2.5 Variations on the Turing machine
• 3. Philosophical Issues Related to Turing Machines
  • 3.1 Human and Machine Computations
  • 3.2 Thesis, Definition, Axioms or Theorem
• 4. Alternative Historical Models of Computability
  • 4.1 General Recursive Functions
  • 4.2 λ-Definability
  • 4.3 Post Production Systems
  • 4.4 Formulation 1
• 5. Impact of Turing Machines on Computer Science
  • 5.1 Impact on Theoretical Computer Science
  • 5.2 Turing Machines and the Modern Computer
  • 5.3 Theories of Programming
• Bibliography
• Academic Tools
• Other Internet Resources
  • Busy Beaver
  • The Halting Problem
  • Online Turing Machine Simulators
    • Software simulators
    • Hardware simulators
• Related Entries

1. Definitions of the Turing Machine

1.1 Turing’s Definition

Turing introduced Turing machines in the context of research into thefoundations of mathematics. More particularly, he used these abstractdevices to prove that there is no effective general method orprocedure to solve, calculate or compute every instance of thefollowing problem:

Entscheidungsproblem The problem to decidefor every statement in first-order logic (the so-called restrictedfunctional calculus, see the entry onclassical logic for an introduction) whether or not it is derivable in thatlogic.

Note that in its original form (Hilbert & Ackermann 1928), theproblem was stated in terms of validity rather than derivability.Given Gödel’s completeness theorem (Gödel 1929)proving that there is an effective procedure (or not) for derivabilityis also a solution to the problem in its validity form. In order totackle this problem, one needs a formalized notion of “effectiveprocedure” and Turing’s machines were intended to doexactly that.

In what follows, we provide a definition of Turing machines that staysquite close to Turing’s original definition but using a morestandard notation. Note that Turing, in his paper, did not provide astable definition nor notation but introduced a variety of notations(Post 1947, Mélès 2020/21). A Turing machine then, or acomputing machine as Turing called it, in Turing’soriginal definition is a theoretical machine which can be in a finitenumber of configurations \(q_{1},\ldots,q_{n}\) (the states of themachine, calledm-configurations by Turing). It is suppliedwith a one-way infinite and one-dimensional tape divided into squareseach capable of carrying exactly one symbol. At any moment, themachine is scanning the content ofone squarerwhich is either blank (symbolized by \(S_0\)) or contains a symbol\(S_{1},\ldots ,S_{m}\) with \(S_1 = 0\) and \(S_2 = 1\).

The machine is an automatic machine (\(a\)-machine) which means thatat any given moment, the behavior of the machine is completelydetermined by the current state and symbol (called theconfiguration) being scanned. This is the so-calleddeterminacy condition (Section 3). Thesea-machines are contrasted with the so-called choicemachines for which the next state depends on the decision of anexternal device or operator (Turing 1936–7: 232). A Turingmachine is capable of three types of action:

1. Print \(S_i\), move one square to the left (L) and go tostate \(q_{j}\)
2. Print \(S_i\), move one square to the right (R) and go tostate \(q_{j}\)
3. Print \(S_i\), do not move (N) and go to state\(q_{j}\)

The ‘program’ of a Turing machine can then be written as afinite set of quintuples of the form:

Where \(q_i\) is the current state, \(S_j\) the content of the squarebeing scanned, \(S_{i,j}\) the new content of the square; \(M_{i,j}\)specifies whether the machine is to move one square to the left, tothe right or to remain at the same square, and \(q_{i,j}\) is the nextstate of the machine. These quintuples are also called the transitionrules of a given machine. The Turing machine \(T_{\textrm{Simple}}\)which, when started from a blank tape, computes the sequence\(S_0S_1S_0S_1\ldots\) is then given byTable 1.

Note that \(T_{\textrm{Simple}}\) will never enter a configurationwhere it is scanning \(S_1\) so that two of the four quintuples areredundant. Another well-known format to represent the‘program’ of a Turing machine and which was also used byTuring is thetransition table.Table 2 gives the transition table of \(T_{\textrm{Simple}}\).

Where current definitions of Turing machines usually have only onetype of symbols (usually just 0 and 1; it was proven by Shannon thatany Turing machine can be reduced to a binary Turing machine (Shannon1956)) Turing also consideredcomputing machines that use twokinds of symbols: thefigures which consist entirely of 0sand 1s and the so-calledsymbols of the second kind. Theseare differentiated on the Turing machine tape by using a system ofalternating squares of figures and symbols of the second kind. Onesequence of alternating squares contains the figures and is called thesequence ofF-squares. It contains thesequence computedby the machine; the other is called the sequence ofE-squares. The latter are used to markF-squares andare there to “assist the memory” (Turing 1936–7:232). The content of theE-squares is liable to change.F-squares however cannot be changed which means that onecannot implement algorithms whereby earlier computed digits need to bechanged. Moreover, the machine will never print a symbol on anF-square if theF-square preceding it has not beencomputed yet. This usage ofF andE-squares can bequite useful (seeSec. 2.3) but, as was shown by Emil L. Post, it results in a number ofcomplications (seeSec. 1.2).

There are two important observations to be made concerning theabstract nature of Turing’sautomatic machine. Thefirst concerns the definition of the machine itself, namely that themachine’s tape is infinite which corresponds to the assumptionof an infinite memory. The second concerns the definition of a Turingcomputable function, namely that a function is considered Turingcomputable if there exists a set of instructions that will result in aTuring machine computing the function regardless of the amount of timeit takes. One can think of this as assuming the availability ofpotentially infinite time to complete the computation.

These two assumptions are intended to ensure that the definition ofcomputation that results is not too narrow. It ensures that nocomputable function will fail to be Turing-computable solely becausethere is insufficient time or memory to complete the computation. Itfollows that there is an important distinction to be made between whatis computable in theory and computable in practice. Indeed, someTuring computable functions for instance may not ever be computable inpractice, since they may require more memory than can be built usingall of the (finite number of) atoms in the universe.If thenwe accept the Turing machine model as a reasonable model of the moderncomputer, then any result which shows that a function is not Turingcomputable is very strong, since it would imply that no computer thatwe could ever build could carry out the computation. In Section 2.4,it is shown that there are functions which are notTuring-computable.

1.2 Post’s Definition

Turing’s definition was standardized through (some of)Post’s modifications of it in Post 1947. In that paper Postproves that a certain problem from mathematics known as Thue’sproblem or the word problem for semi-groups is not Turing computable(or, in Post’s words, recursively unsolvable). Roughly speaking,Post’s main strategy was to show that if it were decidable thenthe following decision problem from Turing 1936–7 would also bedecidable:

PRINT? The problem to decide for every Turing machineM whether or not it will ever print some symbol (forinstance, 0).

It was however proven by Turing thatPRINT? is notTuring computable and so the same holds true of Thue’sproblem.

While the uncomputability ofPRINT? plays a centralrole in Post’s proof, Post believed that Turing’s proof ofthat was affected by the “spurious Turing convention”(Post 1947: 9), viz. the system ofF andE-squares.Thus, Post introduced a modified version of the Turing machine. Themost important differences between Post’s and Turing’sdefinition are:

1. Post’s Turing machine, when in a given state, either prints ormoves and so its transition rules are more ‘atomic’ (itdoes not have the composite operation of moving and printing). Thisresults in the quadruple notation of Turing machines, where eachquadruple is in one of the three forms ofTable 3:

   Table 3: Post’s Quadruplenotation

   \[ \begin{aligned}\hline& q_iS_jS_{i,j}q_{i,j}\\& q_iS_jLq_{i,j}\\& q_iS_jRq_{i,j}\\\hline \end{aligned} \]
2. Post’s Turing machine has only one kind of symbol and sodoes not rely on the Turing system ofF andE-squares.
3. Post’s Turing machine has a two-way infinite tape.
4. Post’s Turing machine halts when it reaches a state forwhich no actions are defined.

Note that Post’s reformulation of the Turing machine is muchrooted in (Post 1936). That short paper introduced a formalism that isalmost identical to Turing’s machines. However, unlike Turing,Post did not focus on the computation of real numbers but on aformalism to define solvability. This explains why Post needed ahalting state, unlike Turing.

(Some of) Post’s modifications of Turing’s definitionbecame part of the definition of the Turing machine in standard workssuch as Kleene 1952 and Davis 1958. Since that time, several(logically equivalent) definitions have been introduced. Today,standard definitions of Turing machines are, in some respects, closerto Post’s Turing machines than to Turing’s machines. Inwhat follows we will use a variant on the standard definition fromMinsky 1967 which uses the quintuple notation but has noEandF-squares and includes a special halting stateH. It also has only two move operations, viz.,L andR and so the action whereby the machine merely prints is notused. When the machine is started, the tape is blank except for somefinite portion of the tape. Note that the blank square can also berepresented as a square containing the symbol \(S_0\) or simply 0. Thefinite content of the tape will also be called thedatawordon the tape.

1.3 The Definition Formalized

Talk of “tape” and a “read-write head” isintended to aid the intuition (and reveals something of the time inwhich Turing was writing) but plays no important role in thedefinition of Turing machines. In situations where a formal analysisof Turing machines is required, it is appropriate to spell out thedefinition of the machinery and program in more mathematical terms.Purely formally a Turing machine can be specified as a quadruple \(T =(Q,\Sigma, s, \delta)\) where:

• Q is a finite set of statesq
• \(\Sigma\) is a finite set of symbols
• s is the initial state \(s \in Q\)

• \(\delta\) is a transition function determining the next move:

  \[\delta : (Q \times \Sigma) \rightarrow (\Sigma \times \{L,R\} \times Q)\]

The transition function for the machineT is a function fromcomputation states to computation states. If \(\delta(q_i,S_j) =(S_{i,j},D,q_{i,j})\), then when the machine’s state is \(q_j\),reading the symbol \(S_j\), \(T\) replaces \(S_j\) by \(S_{i,j}\),moves in direction \(D \in \{L,R\}\) and goes to state\(q_{i,j}\).

1.4 Describing the Behavior of a Turing Machine

We introduce a representation which allows us to describe the behavioror dynamics of a Turing machine \(T_n\), relying on the notation ofthecomplete configuration (Turing 1936–7: 232) alsoknown today asinstantaneous description (ID) (Davis 1982:6). At any stage of the computation of \(T_{i}\) its ID is givenby:

• (1)the content of thetape, that is, its data word
• (2)the location of thereading head
• (3)the machine’sinternal state

So, given some Turing machineT which is in state \(q_{i}\)scanning the symbol \(S_{j}\), its ID is given by \(Pq_{i}S_{j}Q\)whereP andQ are the finite words to the left andright hand side of the square containing the symbol \(S_{j}\).Figure 1 gives a visual representation of an ID of some Turing machineT in state \(q_i\) scanning the tape.

Figure 1: A complete configuration ofsome Turing machineT. [Anextended description of figure 1 is in the supplement.]

The notation thus allows us to capture the developing behavior of themachine and its tape through its consecutive IDs.Figure 2 gives the first few consecutive IDs of \(T_{\textrm{Simple}}\) usinga graphical representation. Its simulated behavior can be accessedhere.

Figure 2: The dynamics of\(T_{\textrm{Simple}}\) graphical representation.(The animation can be started by clicking on the picture and thenusing the left and right arrows to move through it.)[Anextended description of figure 2 is in the supplement.]

One can also explicitly print the consecutive IDs, using theirsymbolic representations. This results in a so-called state-spacediagram of the behavior of a Turing machine. So, for\(T_{\textrm{Simple}}\) we get (Note that \(\overline{0}\) means theinfinite repetition of 0s):

2. Computing with Turing Machines

As explained inSec. 1.1, Turing machines were originally intended to formalize the notion ofcomputability in order to tackle a fundamental problem of mathematics.Independently of Turing, Emil Post (Post 1936) andAlonzo Church (Church 1936) gave a different but logically equivalent formulation(seeSec. 4). Today, most computer scientists agree that Turing’s, or anyother logically equivalent, formal notion capturesallcomputable problems, viz. it is assumed that for any computableproblem, there exists a Turing machine which computes it. This isknown as theChurch-Turing thesis,Turing’sthesis (when the reference is only to Turing’s work) orChurch’s thesis (when the reference is only toChurch’s work). Note that this does not say anything about themany basicintensional differences between the broad variety of computationally equivalent formaldevices that have been developed since Turing’s time. That is,computability here is interpreted extensionally (what can be computed)and not in an operational manner (how it is being computed) (Martini2020).

The thesis implies that, if accepted, any problem not computable by aTuring machine is not computable by any finite means whatsoever.Indeed, since it was Turing’s ambition to capture “[all]the possible processes which can be carried out in computing anumber” (Turing 1936–7: 249), it follows that, if weaccept Turing’s analysis:

• Any problem not computable by a Turing machine is not“computable” in the absolute sense (at least, absoluterelative to humans, seeSection 3).
• For any problem that we believe is computable, we should be ableto construct a Turing machine which computes it. To put it inTuring’s wording:

  It is my contention that [the] operations [of a computing machine]include all those which are used in the computation of a number.(Turing 1936–7: 231)

In this section, examples will be given which illustrate thecomputational power and boundaries of the Turing machine model.Section 3 then discusses some philosophical implications related toTuring’s thesis with respect to the Turing machine model.

2.1 Some (Simple) Examples

In order to speak about a Turing machine that does something usefulfrom the human perspective, we will have to provide an interpretationof the symbols recorded on the tape. For example, if we want to designa machine which will compute some mathematical function, addition say,then we will need to describe how to interpret the ones and zerosappearing on the tape as numbers.

In the examples that follow we will represent the numbern asa block of \(n+1\) copies of the symbol ‘1’ on the tape.Thus we will represent the number 0 as a single ‘1’ andthe number 3 as a block of four ‘1’s. This is calledunary notation.

We will also have to make some assumptions about the configuration ofthe tape when the machine is started, and when it finishes, in orderto interpret the computation. We will assume that if the function tobe computed requiresn arguments, then the Turing machinewill start with its head scanning the leftmost ‘1’ of asequence ofn blocks of ‘1’s. The blocks of‘1’s representing the arguments must be separated by asingle occurrence of the symbol ‘0’. For example, tocompute the sum \(3+4\), a Turing machine will start in theconfiguration shown inFigure 3.

Figure 3: Initial configuration for acomputation over two numbersn andm. [Anextended description of figure 3 is in the supplement.]

Here the supposed addition machine takes two arguments representingthe numbers to be added, starting at the leftmost 1 of the firstargument. The arguments are separated by a single 0 as required, andthe first block contains four ‘1’s, representing thenumber 3, and the second contains five ‘1’s, representingthe number 4.

A machine must finish in standard configuration too. There must be asingle block of symbols (a sequence of 1s representing some number ora symbol representing another kind of output) and the machine must bescanning the leftmost symbol of that sequence. If the machinecorrectly computes the function then this block must represent thecorrect answer.

Addition of two numbersn andm

Table 4 gives the transition table of a Turing machine \(T_{\textrm{Add}_2}\)which adds two natural numbersn andm. We assumethe machine starts in state \(q_1\) scanning the leftmost 1 of the\(n+1\) 1s representingn.

The idea of doing an addition with Turing machines when using unaryrepresentation is to shift the leftmost numbern one squareto the right. This is achieved by erasing the leftmost 1 of the \(n+1\) 1s (this is done in state \(q_1\)) and then setting the 0 betweenthe \(n+1\) and \(m+1\) 1s to 1 (state \(q_2\)). We then have \(n + m+ 2\) 1s on the tape and so we still need to erase one additional 1.This is done by erasing the leftmost 1 (states \(q_3\) and \(q_4\)).Figure 4 shows this computation for \(3 + 4\).

Figure 4: The computation of \(3+4\) by\(T_{\textrm{Add}_2}\)(The animation can be started by clicking on the picture and thenusing the left and right arrows to move through it.) A fullsimulation, with the possibility of changing the input and thebehavior, can be foundhere [Anextended description of figure 4 is in the supplement.]

Addition ofn numbers

We can generalize \(T_{\textrm{Add}_2}\) to a Turing machine\(T_{\textrm{Add}_i}\) for the addition of an arbitrary numberi of integers \(n_1, n_2,\ldots, n_j\). We assume again thatthe machine starts in state \(q_1\) scanning the leftmost 1 of\(n_1+1\) 1s. The transition table for such a machine\(T_{\textrm{Add}_i}\) is given inTable 5.

The machine \(T_{\textrm{Add}_i}\) uses the principle of shifting theaddends to the right which was also used for \(T_{\textrm{Add}_2}\).More particularly, \(T_{add_i}\) computes the sum of \(n_1 + 1\),\(n_2 + 1\),… \(n_i+1\) from left to right, viz. it computesthis sum as follows:

The most important difference between \(T_{\textrm{Add}_2}\) and\(T_{\textrm{Add}_i}\) is that \(T_{\textrm{Add}_i}\) needs to verifyif the leftmost addend \(N_j, 1 < j \leq i\) is equal to \(N_i\).This is achieved by checking whether the first 0 to the right of\(N_j\) is followed by another 0 or not (states \(q_2\) and \(q_3\)).If it is not the case, then there is at least one more addend\(n_{j+1}\) to be added. Note that, as was the case for\(T_{\textrm{Add}_2}\), the machine needs to erase an additional onefrom the addend \(n_{j+1}\) which is done via state \(q_5\). It thenmoves back to state \(q_1\). If, on the other hand, \(N_j = N_i\), themachine moves to the leftmost 1 of \(N_i = n_1 + n_2 + \ldots + n_i +1 \) and halts. A full simulation, with the possibility of changingthe input and the behavior of \(T_{\textrm{Add}_i}\), can be accessedhere

2.2 Computable Numbers and Decision Problems

Turing’s original paper is concerned withcomputable (real)numbers. A (real) number is Turing computable if there exists aTuring machine which computes an arbitrarily precise approximation tothat number. All of the algebraic numbers (roots of polynomials withalgebraic coefficients) and many transcendental mathematicalconstants, such ase and \(\pi\) are Turing-computable.Turing gave several examples of classes of numbers computable byTuring machines as a heuristic argument showing that a wide diversityof classes of numbers can be computed by Turing machines (see section10Examples of large classes of numbers which are computablein Turing 1936–7).

One might wonder however in what sense computation with numbers, viz.calculation, capturesnon-numerical but computable problemsand so how Turing machines are supposed to captureallgeneral and effective procedures which determine whether something isthe case or not. Examples of such problems are:

• “decide for any givenx whether or notxdenotes a prime”
• “decide for any givenx whether or notxis the description of a Turing machine”.

In general, these problems are of the form:

• “decide for any givenx whether or notxhas propertyX”

An important challenge of both theoretical and concrete advances incomputing (often at the interface with other disciplines) has becomethe problem of providing an interpretation ofX such that itcan be tackled computationally. To give just one concrete example, indaily computational practices it might be important to have a methodto decide for any digital “source” whether or not it canbe trusted and so one needs a computational interpretation oftrust.

Thecharacteristic function of a predicate is a functionwhich has the value TRUE or FALSE when given appropriate arguments. Inorder for such functions to be computable, Turing relied onGödel’s insight that these kind of problems can be encodedas a problem about numbers (SeeGödel’s incompleteness theorem and the nextSec. 2.3) In Turing’s wording:

The expression “there is a general process for determining…” has been used [here] […] as equivalent to“there is a machine which will determine …”. Thisusage can be justified if and only if we can justify our definition of“computable”. For each of these “generalprocess” problems can be expressed as a problem concerning ageneral process for determining whether a given integern hasa property \(G(n)\) [e.g. \(G(n)\) might mean “n issatisfactory” or “n is the Gödelrepresentation of a provable formula”], and this is equivalentto computing a number whosen-th figure is 1 if \(G(n)\) istrue and 0 if it is false. (1936–7: 248)

It is the possibility of coding the “general process”problems as numerical problems that is essential to Turing’sconstruction of the universal Turing machine and its use within aproof that shows there are problems that cannot be computed by aTuring machine.

2.3 Turing’s Universal Machine

The universal Turing machine which was constructed to prove theuncomputability of certain problems, is, roughly speaking, a Turingmachine that is able to compute what any other Turing machinecomputes. Assuming that the Turing machine notion fully capturescomputability (and so that Turing’s thesis is valid), it isimplied that anything which can be “computed”, can also becomputed by that one universal machine. Conversely, any problem thatis not computable by the universal machine is considered to beuncomputable.

This is the rhetorical and theoretical power of the universal machineconcept, viz. that one relatively simple formal device captures all“the possible processes which can be carried out incomputing a number” (Turing 1936–7). It is also oneof the main reasons why Turing has beenretrospectivelyidentified as one of the founding fathers of computer science (seeSection 5).

So how to construct a universal machineU out of the set ofbasic operations we have at our disposal? Turing’s approach isthe construction of a machineU which is able to (1)‘interpret’ the program ofany other machine\(T_{n}\) and, based on that “interpretation”, (2)‘mimic’ the behavior of \(T_{n}\). To this end, a methodis needed so that the program and the behavior of \(T_n\) are, to acertain extend, interchangeable since both aspects are to bemanipulated on the same tape and by the same machine. This is achievedby Turing in two basic steps: the development of (1) a notationalmethod and (2) a set of elementary functions which treats thatnotation—independent of whether it is formalizing the program orthe behavior of \(T_n\)—as text to be compared, copied down,erased, etc. In other words, Turing develops a technique that allowsto treat program and behavior of a Turing machine on the samelevel.

2.3.1 Interchangeability of program and behavior: a notation

Given some machine \(T_n\), Turing’s basic idea is to constructa machine \(T_n'\) which, rather than directly printing the output of\(T_n\), prints out the successive complete configurations orinstantaneous descriptions of \(T_n\). In order to achieve this,\(T_n'\):

[…] could be made to depend on having the rules of operation[…] of [\(T_n\)] written somewhere within itself […]each step could be carried out by referring to these rules. (Turing1936–7: 242)

In other words, \(T_n'\) prints out the successive completeconfigurations of \(T_n\) by having the program of \(T_n\) written onits tape. Thus, Turing needs a notational method which makes itpossible to ‘capture’ two different aspects of a Turingmachine on one and the same tape in such a way they can be treatedby the same machine, viz.:

• (1) its description interms ofwhat it should do—the quintuplenotation
• (2) its description interms ofwhat it is doing—the complete configurationnotation

Thus, a first and perhaps most essential step, in the construction ofU are the quintuple and complete configuration notation andthe idea of putting them on the same tape. More particularly, the tapeis divided into two regions which we will call theA andB region here. TheA region contains a notation ofthe ‘program’ of \(T_n\) and theB region anotation for the successive complete configurations of \(T_n\). InTuring’s paper they are separated by an additional symbol“::”.

To simplify the construction ofU and in order to encode anyTuring machine as a unique number, Turing develops a third notationwhich permits to express the quintuples and complete configurationswith letters only. This is determined by [Note that we useTuring’s original encoding. Of course, there is a broad varietyof possible encodings, including binary encodings]:

• Replacing each state \(q_i\) in a quintuple of \(T_n\) by\[D\underbrace{A\ldots A}_i,\] so, for instance \(q_3\) becomes \(DAAA\).
• Replacing each symbol \(S_{j}\) in a quintuple of \(T_n\) by\[D\underbrace{C\ldots C}_j,\] so, for instance, \(S_1\) becomes \(DC\).

Using this method, each quintuple of some Turing machine \(T_n\) canbe expressed in terms of a sequence of capital letters and so the‘program’ of any machine \(T_{n}\) can be expressed by theset of symbolsA, C, D, R, L, N and ;. This is the so-calledStandard Description (S.D.) of a Turing machine. Thus, forinstance, the S.D. of \(T_{\textrm{Simple}}\) is:

This is, essentially, Turing’s version ofGödel numbering. Indeed, as Turing shows, one can easily get a numerical descriptionrepresentation orDescription Number (D.N.) of a Turingmachine \(T_{n}\) by replacing:

• “A” by “1”
• “C” by “2”
• “D” by “3”
• “L” by “4”
• “R” by “5”
• “N” by “6”
• “;” by “7”

Thus, the D.N. of \(T_{\textrm{Simple}}\) is:

Note that every machine \(T_n\) has a unique D.N.; a D.N. representsone and one machine only.

Clearly, the method used to determine the \(S.D.\) of some machine\(T_n\) can also be used to write out the successive completeconfigurations of \(T_n\). Using “:” as a separatorbetween successive complete configurations, the first few completeconfigurations of \(T_{\textrm{Simple}}\) are:

2.3.2 Interchangeability of program and behavior: a basic set of functions

Having a notational method to write the program and successivecomplete configurations of some machine \(T_n\) on one and the sametape of some other machine \(T_n'\) is the first step inTuring’s construction ofU. However,U shouldalso be able to “emulate” the program of \(T_n\) aswritten in regionA so that it can actually write out itssuccessive complete configurations in regionB. Moreover itshould be possible to “take out and exchange[…] [therules of operations of some Turing machine] for others” (Turing1936–7: 242). Viz., it should be able not just to calculate butalso to compute. It should, for instance, be able to“recognize” whether it is in regionA orB and it should be able to determine whether or not a certainsequence of symbols is the next state \(q_i\) which needs to beexecuted.

This is achieved by Turing through the construction of a sequence ofTuring computable problems such as:

• Finding the leftmost or rightmost occurrence of a sequence ofsymbols
• Marking a sequence of symbols by some symbol \(a\) (remember thatTuring uses two kinds of alternating squares)
• Comparing two symbol sequences
• Copying a symbol sequence

Turing develops a notational technique, calledskeletontables, for these functions which serves as a kind of shorthandnotation for a complete Turing machine table but can be easily used toconstruct more complicated machines from previous ones. The techniqueis quite reminiscent of the recursive technique of composition (see:recursive functions).

To illustrate how such functions are Turing computable, we discuss onesuch function in more detail, viz. the compare function. It isconstructed on the basis of a number of other Turing computablefunctions which are built on top of one another. In order tounderstand how these functions work, remember that Turing used asystem of alternatingF andE-squares where theF-squares contain the actual quintuples and completeconfigurations and theE-squares are used to mark off certainparts of the machine tape. For the comparing then of two sequences ofsymbols \(W_1\) and \(W_2\), each symbol of \(W_1\) will be marked bysome symbol \(a\) and each symbol of \(W_2\) will be marked by somesymbolb.

Turing defined nine different functions to show how the comparefunction can be computed with Turing machines:

• FIND\((q_{i}, q_{j},a)\): this machine function searches for theleftmost occurrence of \(a\). If \(a\) is found, the machine moves tostate \(q_{i}\) else it moves to state \(q_{j}\). This is achieved byhaving the machine first move to the beginning of the tape (indicatedby a special mark) and then to have it move right until it finds \(a\)or reaches the rightmost symbol on the tape.
• FINDL\((q_{i}, q_{j},a)\): the same as FIND but after \(a\) hasbeen found, the machine moves one square to the left. This is used infunctions which need to compute on the symbols inF-squareswhich are marked by symbols \(a\) in theE-squares.
• ERASE\((q_{i},q_{j},a)\): the machine computes FIND. If \(a\) isfound, it erases \(a\) and goes to state \(q_{i}\) else it goes tostate \(q_{j}.\)
• ERASE_ALL\((q_j,a) = \textrm{ERASE}(\textrm{ERASE}\_\textrm{ALL},q_j,a)\): the machines computes ERASE on \(a\) repeatedly until all\(a\)’s have been erased. Then it moves to \(q_{j}.\)
• EQUAL\((q_i,q_j,a)\): the machine checks whether or not thecurrent symbol is \(a\). If yes, it moves to state \(q_i\) else itmoves to state \(q_j.\)
• CMP_XY\((q_i,q_j,b) = \textrm{FINDL(EQUAL}(q_i,q_j,x), q_j, b)\):whatever the current symbolx, the machine computes FINDL onb (and so looks for the symbol marked byb). Ifthere is a symboly marked withb, the machinecomputes \(\textrm{EQUAL}\) onx andy, else, themachine goes to state \(q_j\). In other words, CMP_XY\((q_i,q_j,b)\)compares whether the current symbol is the same as the leftmost symbolmarkedb.
• COMPARE_MARKED\((q_i,q_j,q_n,a,b)\): the machine checks whetherthe leftmost symbols marked \(a\) andb respectively are thesame. If there is no symbol marked \(a\) norb, the machinegoes to state \(q_{n}\); if there is a symbol marked \(a\) and onemarkedb and they are the same, the machine goes to state\(q_i\), else the machine goes to state \(q_j\). The function iscomputed as \(\textrm{FINDL(CMP}\_XY(q_i,q_j,b),\textrm{FIND}(q_j,q_n,b),a).\)
• \(\textrm{COMPARE}\_\textrm{ERASE}(q_iq_j,q_n,a,b)\): the same asCOMPARE_MARKED but when the symbols marked \(a\) andb arethe same, the marks \(a\) andb are erased. This is achievedby computing \(\textrm{ERASE}\) first on \(a\) and then onb.
• \(\textrm{COMPARE}\_\textrm{ALL}(q_j,q_n,a,b)\) The machinecompares the sequencesA andB marked with \(a\) andb respectively. This is done by repeatedly computingCOMPARE_ERASE on \(a\) andb. IfA andBare equal, all \(a\)’s andb’s will have beenerased and the machine moves to state \(q_j\), else, it will move tostate \(q_n\). It is computed by \[\textrm{COMPARE}\_\textrm{ERASE}(\textrm{COMPARE}\_\textrm{ALL}(q_j,q_n,a,b),q_j,q_n,a,b)\]

  and so by recursively calling \(\textrm{COMPARE}\_\textrm{ALL}\).

In a similar manner, Turing defines the following functions:

• \(\textrm{COPY}(q_i,a)\): copy the sequence of symbols marked with\(a\)’s to the right of the last complete configuration anderase the marks.
• \(\textrm{COPY}_{n}(q_i, a_1,a_2,\ldots ,a_n)\): copy down thesequences marked \(a_1\) to \(a_n\) to the right of the last completeconfiguration and erase all marks \(a_i.\)
• \(\textrm{REPLACE}(q_i, a,b)\): replace all letters \(a\) by\(b.\)
• \(\textrm{MARK}\_\textrm{NEXT}\_\textrm{CONFIG}(q_i,a) \): markthe first configuration \(q_iS_j\) to the right of the machine’shead with the letter \(a.\)
• \(\textrm{FIND}\_\textrm{RIGHT}(q_i,a)\): find the rightmostsymbol \(a.\)

Using the basic functions COPY, REPLACE and COMPARE, Turing constructsa universal Turing machine.

Below is an outline of the universal Turing machine indicating howthese basic functions indeed allow for the construction of a Turingmachine which can emulate the behavior of any other Turing machine. Itis assumed that upon initialization,U has on its tape theS.D. of some Turing machine \(T_n\). Remember that Turing uses thesystem of alternatingF andE-squares and so, forinstance, the S.D. of \(T_{\textrm{Simple}}\) will be written on thetape ofU as:

where “_” indicates an unmarkedE-square.

• INIT: To the right of the rightmost quintuple ofT_n,U prints ::_:_D_A_,where _ indicates an unmarkedE-square.

• FIND_NEXT_STATE: The machine first marks (1) withy theconfiguration \(q_{CC,i}S_{CC,j}\) of the rightmost (and so last)complete configuration computed byU in theB partof the tape and (2) withx the configuration\(q_{q,m}S_{q,n}\) of the leftmost quintuple which is not preceded bya marked (with the letterz) semicolon in theA partof the tape. The two configurations are compared. If they areidentical, the machine moves to MARK_OPERATIONS, if not, it marks thesemicolon preceding \(q_{q,m}S_{q,n}\) withz and goes toFIND_NEXT_STATE. This is easily achieved using the functionCOMPARE_ALL which means that, whatever the outcome of the comparison,the marksx andy will be erased. For instance,suppose that \(T_n = T_{\textrm{Simple}}\) and that the last completeconfiguration of \(T_{\textrm{Simple}}\) as computed byUis:

  \[\tag{1} \label{CC_univ} :\_\underbrace{D\_}_{S_0}\underbrace{D\_C\_}_{S_1}\underbrace{D\_}_{S_0}\textcolor{Sienna}{\underbrace{D\_A\_A\_}_{q_{2}}\underbrace{D\_}_{S_0}} \]

  ThenU will move to regionA and determine that thecorresponding quintuple is:

  \[\tag{2}\label{quint_univ} \textcolor{Sienna}{\underbrace{D\_A\_A\_}_{q_{2}}\underbrace{D\_}_{S_{0}}}\underbrace{D\_C\_}_{S_1}\underbrace{R\_}\underbrace{D\_A\_}_{q_1}\]

• MARK_OPERATIONS: The machineU marks the operations that itneeds to execute in order to compute the next complete configurationof \(T_n\). The printing and move (L,R, N) operations are marked withu and the next state withy. All markszare erased. Continuing with our example,U will mark(2)as follows:

  \[D\_A\_A\_D\_\textcolor{DarkOrchid}{DuCuRu}\textcolor{green}{DyAy}\]

• MARK_COMPCONFIG: The last complete configuration of \(T_n\) ascomputed byU is marked into four regions: the configuration\(q_{CC,i}S_{CC,j}\) itself is left unmarked; the symbol justpreceding it is marked with anx and the remaining symbols tothe left or marked withv. Finally, all symbols to the right,if any, are marked withw and a “:” is printed tothe right of the rightmost symbol in order to indicate the beginningof the next complete configuration of \(T_n\) to be computed byU. Continuing with our example,(1) will bemarked as follows byU:

  \[\textcolor{Crimson}{\underbrace{Dv}_{S_0}\underbrace{DvCv}_{S_1}}\textcolor{blue}{\underbrace{Dx}_{S_0}}\underbrace{D\_A\_A\_}_{q_2}\underbrace{D\_}_{S_0}:\_\]

  U then goes to PRINT

• PRINT. It is determined if, in the instructions that have beenmarked in MARK_OPERATIONS, there is an operation Print 0 or Print 1.If that is the case, \(0:\) respectively \(1:\) is printed to theright of the last complete configuration. This is not a necessaryfunction but Turing insisted on havingU print out not justthe (coded) complete configurations computed by \(T_n\) but also theactual (binary) real number computed by \(T_n\).

• PRINT_COMPLETE_CONFIGURATION.U prints the next completeconfiguration and erases all marksu, v, w, x, y. It thenreturns to FIND_NEXT_STATE.U first searches for therightmost letteru, to check which move is needed (R, L,N) and erases the marku forR, L, N. Dependingon the valueL, R orN will then write down the nextcomplete configuration by applying COPY\(_5\) tou, v, w, x,y. The move operation (L, R, N) is accounted for by theparticular combination ofu, v, w, x, y:

  \[\begin{array}{ll}\textrm{When ~} L: & \textrm{COPY}_5(\textrm{FIND}\_\textrm{NEXT}\_\textrm{STATE}, \textcolor{crimson}{v},\textcolor{green}{y},\textcolor{blue}{x},\textcolor{DarkOrchid}{u},\textcolor{RawSienna}{w})\\ \textrm{When ~} R: & \textrm{COPY}_5(\textrm{FIND}\_\textrm{NEXT}\_\textrm{STATE}, \textcolor{crimson}{v},\textcolor{blue}{x},\textcolor{DarkOrchid}{u},\textcolor{green}{y},\textcolor{RawSienna}{w})\\ \textrm{When ~} N: & \textrm{COPY}_5(\textrm{FIND}\_\textrm{NEXT}\_\textrm{STATE}, \textcolor{crimson}{v},\textcolor{blue}{x},\textcolor{green}{y},\textcolor{DarkOrchid}{u},\textcolor{RawSienna}{w}) \end{array}\]

  Following our example, since \(T_{\textrm{Simple}}\) needs to moveright, the new rightmost complete configursiation of\(T_{\textrm{Simple}}\) written on the tape ofU is:

  \[\textcolor{crimson}{\underbrace{D\_}_{S_0}\underbrace{D\_C\_}_{S_1}}\textcolor{blue}{\underbrace{D\_}_{S_0}}\textcolor{DarkOrchid}{\underbrace{D\_C\_}_{S_1}}\textcolor{green}{\underbrace{D\_A\_}_{q_1}} \]

  Since we have that for this complete configuration the square beingscanned by \(T_{\textrm{Simple}}\) is one that was not included in theprevious complete configuration (viz. \(T_{\textrm{Simple}}\) hasreached beyond the rightmost previous point) the completeconfiguration as written out byU is in fact incomplete. Thissmall defect was corrected by Post (Post 1947) by including anadditional instruction in the function used to mark the completeconfiguration in the next round.

As is clear, Turing’s universal machine indeed requires thatprogram and ‘data’ produced by that program aremanipulated interchangeably, viz. the program and its productions areput next to each other and treated in the same manner, as sequences ofletters to be copied, marked, erased and compared. Therein lies thecombinatorial and textual character of computability as defined byTuring and others (Lassègue and Longo 2012). There is nothingmagical or mysterious about its computation.

Turing’s particular construction is quite intricate with itsreliance on theF andE-squares, the use of a ratherlarge set of symbols and a rather arcane notation used to describe thedifferent functions discussed above. Since 1936 several modificationsand simplifications have been implemented. The removal of thedifference betweenF andE-squares was alreadydiscussed inSection 1.2 and it was proven by Shannon that any Turing machine, including theuniversal machine, can be reduced to a binary Turing machine (Shannon1956). Since the 1950s, there has been quite some research on whatcould be the smallest possible universal devices (with respect to thenumber of states and symbols) and quite some “small”universal Turing machines have been found. These results are usuallyachieved by relying on other equivalent models of computability suchas, for instance, tag systems. For a survey on research into smalluniversal devices (see Margenstern 2000; Woods & Neary 2009).

2.4 The Halting Problem and the Entscheidungsproblem

As explained, the purpose of Turing’s paper was to show that theEntscheidungsproblem for first-order logic is not computable. The sameresult was achieved independently by Church (1936a, 1936b) using adifferent kind of formal device which is logically equivalent to aTuring machine (seeSec. 4). The result went very much against what Hilbert had hoped to achievewith his finitary and formalist program. Indeed, next toGödel’s incompleteness results, they broke much ofHilbert’s dream of making mathematics void ofIgnorabimus as expressed in the following words ofHilbert:

The true reason why Comte could not find an unsolvable problem, liesin my opinion in the assertion that there exists no unsolvableproblem. Instead of the stupid Ignorabimus, our solution should be: Wemust know. We shall know. (1930: 963) [translation by the author]

Note that the solvability Hilbert is referring to here concernssolvability of mathematical problems in general and not justmechanically solvable. It is shown however in Mancosu et al. 2009 (p.94), that this general aim of solving every mathematical problem,underpins two particular convictions of Hilbert namely that (1) theaxioms of number theory are complete and (2) that there are noundecidable problems in mathematics.

2.4.1 Direct and indirect proofs of uncomputable decision problems

So, how can one show, for a particular decision problem\(\textrm{D}_i\), that it is not computable? There are two mainmethods:

• Indirect proof: take some problem\(\textrm{D}_{\textrm{uncomp}}\) which is already known to beuncomputable and show that the problem “reduces” to\(\textrm{D}_{i}\).
• Direct proof: prove the uncomputability of\(\textrm{D}_{i}\) directly by assuming some version of theChurch-Turing thesis.

Today, one usually relies on the first method while it is evident thatin the absence of a problem \(\textrm{D}_{\textrm{uncomp}}\), Turingbut also Church and Post (seeSec. 4) had to rely on the direct approach.

The notion of reducibility has its origins in the work of Turing andPost who considered several variants (Post 1947; Turing 1939). Theconcept was later appropriated in the context of computationalcomplexity theory and is today one of the basic concepts of bothcomputability and computational complexity theory (Odifreddi 1989;Sipser 1996). Roughly speaking, a reduction of a problem \(D_i\) to aproblem \(D_j\) comes down to providing an effective procedure fortranslating every instance \(d_{i,m}\) of the problem \(D_i\) to aninstance \(d_{j,n}\) of \(D_j\) in such a way that an effectiveprocedure for solving \(d_{j,n}\) also yields an effective procedurefor solving \(d_{i,m}\). In other words, if \(D_i\) reduces to \(D_j\)then, if \(D_i\) is uncomputable so is \(D_j\). Note that thereduction of one problem to another can also be used in decidabilityproofs: if \(D_i\) reduces to \(D_j\) and \(D_j\) is known to becomputable then so is \(D_i\).

In the absence ofD\(_{\textrm{uncomp}}\) a verydifferent approach was required and Church, Post and Turing each usedmore or less the same approach to this end (Gandy 1988). First of all,one needs a formalism which captures the notion of computability.Turing proposed the Turing machine formalism to this end. A secondstep is to show that there are problems that are not computable withinthe formalism. To achieve this, a uniform processUneeds to be set-up relative to the formalism which is able to computeevery computable number. One can then use (some form of)diagonalization in combination withU to derive acontradiction. Diagonalization was introduced by Cantor to show thatthe set of real numbers is “uncountable” or notdenumerable. A variant of the method was used also by Gödel inthe proof of hisfirst incompleteness theorem.

2.4.2 Turing’s basic problem CIRC?, PRINT? and the Entscheidungsproblem

Recall that in Turing’s original version of the Turing machine,the machines are computing real numbers. This implied that a“well-behaving” Turing machine should in fact never haltand print out an infinite sequence of figures. Such machines wereidentified by Turing ascircle-free. All other machines arecalledcircular machines. A numbern which is theD.N. of a circle-free machine is calledsatisfactory.

This basic difference is used in Turing’s proof of theuncomputability of:

CIRC? The problem to decide for every numbern whether or not it is satisfactory

The proof of the uncomputability ofCIRC? uses theconstruction of a hypothetical and circle-free machine \(T_{decide}\)which computes the diagonal sequence of the set of all computablenumbers computed by the circle-free machines. Hence, it relies for itsconstruction on the universal Turing machine and a hypotheticalmachine that is able to decideCIRC? for each numbern given to it. It is shown that the machine \(T_{decide}\)becomes a circular machine when it is provided with its owndescription number, hence the assumption of a machine which is capableof solvingCIRC? must be false.

Based on the uncomputability ofCIRC?, Turing thenshows that alsoPRINT? is not computable. Moreparticularly he shows that ifPRINT? were to becomputable, alsoCIRC? would be decidable, viz. herephrasesPRINT? in such a way that it becomes theproblem to decide for any machine whether or not it will print aninfinity of symbols which would amount to decidingCIRC?.

Finally, based on the uncomputability ofPRINT?Turing shows that the Entscheidungsproblem is not decidable. This isachieved by showing:

1. how for each Turing machineT, it is possible toconstruct a corresponding formulaT in first-orderlogic and
2. if there is a general method for determining whetherT is provable, then there is a general method forproving thatT will ever print 0. This is the problemPRINT? and so cannot be decidable (provided we acceptTuring’s thesis).

It thus follows from the uncomputability ofPRINT?,that the Entscheidungsproblem is not computable.

2.4.3 The halting problem

Given Turing’s focus on computable real numbers, his basedecision problem is about determining whether or not some Turingmachine willnot halt and so is not quite the same as themore well-known halting problem:

Note that Turing’s problemPRINT? is very closetoHALT? (see Davis 1958: Chapter 5, Theorem2.3).

A popular proof ofHALT? goes as follows. Assume thatHALT? is computable. Then it should be possible toconstruct a Turing machine which decides, for each machine \(T_i\) andsome inputw for \(T_i\) whether or not \(T_i\) will halt onw. Let us call this machine \(T_{H}\). More particularly, wehave:

We now define a second machine \(T_D\) which relies on the assumptionthat the machine \(T_H\) can be constructed. More particularly, wehave:

If we now set \(T_i\) to \(T_D\) we end up with a contradiction: if\(T_D\) halts it means that \(T_D\) does not halt and vice versa. Apopular but quite informal variant of this proof was given byChristopher Strachey in the context of programming (Strachey 1965,Daylight 2021).

2.5 Variations on the Turing machine

As is clear fromSections 1.1 and1.2, there is a variety of definitions of the Turing machine. One can usea quintuple or quadruple notation; one can have different types ofsymbols or just one; one can have a two-way infinite or a one-wayinfinite tape; etc. Several other less obvious modifications have beenconsidered and used in the past. These modifications can be of twokinds: generalizations or restrictions. These do not result in“stronger” or “weaker” models. Viz. thesemodified machines compute no more and no less than the Turingcomputable functions. This adds to the robustness of the Turingmachine definition.

Binary machines

In his short 1936 note Post considers machines that either mark orunmark a square which means we have only two symbols \(S_0\) and\(S_1\) but he did not prove that this formulation captures exactlythe Turing computable functions. It was Shannon who proved that forany Turing machineT withn symbols there is aTuring machine with two symbols that simulatesT (Shannon1956). He also showed that for any Turing machine withmstates, there is a Turing machine with only two states that simulatesit.

Non-erasing machines

Non-erasing machines are machines that can only overprint \(S_0\). InMoore 1952, it was mentioned that Shannon proved that non-erasingmachines can compute what any Turing machine computes. This result wasgiven in a context of actual digital computers of the 50s which reliedon punched tape (and so, for which, one cannot erase). Shannon’sresult however remained unpublished. It was Wang who published theresult (Wang 1957).

Non-writing machines

It was shown by Minsky that for every Turing machine there is anon-writing Turing machine with two tapes that simulates it (Minsky1961, 438–445)

Multiple tapes

Instead of one tape one can consider a Turing machine with multipletapes. This turned out the be very useful in several differentcontexts. For instance, Minsky, used two-tape non-writing Turingmachines to prove that a certain decision problem defined by Post (thedecision problem for tag systems) is non-Turing computable (Minsky1961). Hartmanis and Stearns then, in their founding paper forcomputational complexity theory, proved that anyn-tapeTuring machine reduces to a single tape Turing machine and so anythingthat can be computed by ann-tape or multitape Turing machinecan also be computed by a single tape Turing machine, and conversely(Hartmanis & Stearns 1965). They used multitape machines becausethey were considered to be closer to actual digital computers.

n-dimensional Turing machines

Another variant is to consider Turing machines where the tape is notone-dimensional butn-dimensional. This variant too reducesto the one-dimensional variant.

Non-deterministic machines

An apparently more radical reformulation of the notion of Turingmachine is that of non-deterministic Turing machines. As explained in1.1, one fundamental condition of Turing’s machines is the so-calleddeterminacy condition, viz. the idea that at any given moment, themachine’s behavior is completely determined by the configurationor state it is in and the symbol it is scanning. Next to these, Turingalso mentions the idea of choice machines for which the next state isnot completely determined by the state and symbol pair. Instead, someexternal device makes a random choice of what to do next.Non-deterministic Turing machines are a kind of choice machines: foreach state and symbol pair, the non-deterministic machine makes anarbitrary choice between a finite (possibly zero) number of states.Thus, unlike the computation of a deterministic Turing machine, thecomputation of a non-deterministic machine is a tree of possibleconfiguration paths. One way to visualize the computation of anon-deterministic Turing machine is that the machine spawns an exactcopy of itself and the tape for each alternative available transition,and each machine continues the computation. If any of the machinesterminates successfully, then the entire computation terminates andinherits that machine’s resulting tape. Notice the wordsuccessfully in the preceding sentence. In this formulation, somestates are designated asaccepting states and when themachine terminates in one of these states, then the computation issuccessful, otherwise the computation is unsuccessful and any othermachines continue in their search for a successful outcome. Theaddition of non-determinism to Turing machines does not alter theextent of Turing-computability. Non-determinism was introduced forfinite automata in the paper, Rabin & Scott 1959, where it is alsoshown that adding non-determinism does not result in more powerfulautomata. Non-deterministic Turing machines are an important model inthe context ofcomputational complexity theory.

Weak and semi-weak machines

Weak Turing machines are machines where some word over the alphabet isrepeated infinitely often to the left and right of the input.Semi-weak machines are machines where some word is repeated infinitelyoften either to the left or right of the input. These machines aregeneralizations of the standard model in which the initial tapecontains some finite word (possibly nil). They were introduced todetermine smaller universal machines. Watanabe was the first to definea universal semi-weak machine with six states and five symbols(Watanabe 1961). Recently, a number of researchers have determinedseveral small weak and semi-weak universal Turing machines (e.g.,Woods & Neary 2007; Cook 2004)

Besides these variants on the Turing machine model, there are variantsthat result in models which capture, in some well-defined sense, morethan the (Turing)-computable functions. Examples of such models areoracle machines (Turing 1939), trial-and-error machines (Putnam 1965),infinite-time Turing machines (Hamkins & Lewis 2008) andaccelerating Turing machines (Copeland 2002). There are variousreasons for introducing such “stronger” models. Some arewell-known models of computability and recursion theory and are usedin the theory of higher-order recursion and relative computability(oracle machines); others, like the accelerating machines, wereintroduced in the context ofsupertasks and the idea of providing physical models that “compute”functions which are not Turing-computable. Note however that suchmodels do not provide aneffective method to solveincomputable problems such as the halting problem. Still others wereintroduced to offer elaborations to the notion of computation (thinkof trial-and-error computation) or to provide models that are“closer” to actual computational practices. See alsoSec. 3.1.

3. Philosophical Issues Related to Turing Machines

3.1 Human and Machine Computations

In its original context, Turing’s identification between thecomputable numbers and Turing machines was aimed at proving that theEntscheidungsproblem isnot a computable problem and so isnot a so-called “general process” problem (Turing1936–7: 248). The basic assumption to be made for this result tobe valid is that our “intuitive” notion of computabilitycan be formally defined as Turing computability and so that there areno “computable” problems that are not Turing computable.But what was Turing’s “intuitive” notion ofcomputability and how can we be sure that it really covers allcomputable problems, and, more generally, all kinds of computations?This is a very basic question in thephilosophy of computer science.

At the time Turing was writing his paper, the modern computer was notdeveloped yet and so rephrasings of Turing’s thesis whichidentify Turing computability with computability by a modern computerare interpretations rather than historically correct statements ofTuring’s thesis. The existing computing machines at the timeTuring wrote his paper, such as the differential analyzer or deskcalculators, were quite restricted in what they could compute and wereused in a context of human computational practices (Grier 2007). It isthus not surprising that Turing did not attempt to formalize machinecomputation but rather human computation and so computable problems inTuring’s paper become computable by human means. This is veryexplicit in Section 9 of Turing 1936–7 where he shows thatTuring machines are a ‘natural’ model of (human)computation by analyzing the process of human computation. Theanalysis results in a kind of abstract human ‘computor’who fulfills a set of different conditions that are rooted inTuring’s recognition of a set of human limitations whichrestrict what we can compute (of our sensory apparatus but also of ourmental apparatus). This ‘computor’ computes (real) numberson an infinite one-dimensional tape divided into squares [Note: Turingassumed that the reduction of the 2-dimensional character of the papera human mathematician usually works on “is not essential ofcomputation” (Turing 1936–7: 249)]. It has the followingrestrictions (Gandy 1988; Sieg 1994):

• Determinacy condition D “The behaviour ofthe computer at any moment is determined by the symbols which they areobserving and his ‘state of mind’ at that moment.”(Turing 1936–7: 250)
• Boundedness condition B1 “there is a boundB to the number of symbols or squares which the computer can observeat one moment. If they wish to observe more, they must use successiveobservations.” (Turing 1936–7: 250)
• Boundedness condition B2 “the number ofstates of mind which need be taken into account is finite”(Turing 1936–7: 250)
• Locality condition L1 “We may […]assume that the squares whose symbols are changed are always‘observed’ squares.” (Turing 1936–7: 250)
• Locality condition L2 “each of the newobserved squares is withinL squares of an immediatelypreviously observed square.” (Turing 1936–7: 250)

It is this so-called “direct appeal to intuition”(1936–7: 249) of Turing’s analysis and resulting modelthat explain why the Turing machine is today considered by many as thebest standard model of computability (for a strong statement of thispoint of view, see Soare 1996). Indeed, from the above set ofconditions one can quite easily derive Turing’s machines. Thisis achieved basically by analyzing the restrictive conditions into“‘simple operations’ which are so elementary that itis not easy to imagine them further divided” (Turing1936–7: 250).

The focus on human computation in Turing’s analysis ofcomputation, has led researchers to extend Turing’s analysis tocomputation by physical devices. This results in (versions of) theso-called physical Church-Turing thesis. Robin Gandy focused onextending Turing’s analysis to discrete mechanical devices (notethat he did not consider analog machines). More particularly, likeTuring, Gandy starts from a basic set of restrictions of computationby discrete mechanical devices and, on that basis, develops a newmodel which he proved to be reducible to the Turing machine model.This work is continued by Wilfried Sieg who proposed the framework ofComputable Dynamical Systems (Sieg 2008). Others have considered thepossibility of “reasonable” models from physics which“compute” something that is not Turing computable. See forinstance Aaronson, Bavarian, & Gueltrini 2024 [Other InternetResources] in which it is shown thatif closed timelikecurves would exist, the halting problem would become solvable withfinite resources. Others have proposed alternative models forcomputation which are inspired by the Turing machine model but capturespecific aspects of current computing practices for which the Turingmachine model is considered less suited. One example here are thepersistent Turing machines (Goldin 2000) intended to captureinteractive processes. These and other related proposals have beenconsidered by some authors as reasonable models of computation thatsomehow compute more than Turing machines. It is the latter kind ofstatements that became affiliated with research on so-calledhypercomputation resulting in the early 2000s in a rather fiercedebate in the computer science community, see, e.g., Teuscher 2004 forvarious positions. More recently, it was argued that the executionmodel that results from Turing machines are not suitable to captureinteractive computation and that, by consequence, the Turing machinemodel does not provide a satisfactory mechanistic explanation ofinteractive computation (Martin et al. 2023). Unlike earlier work inthis direction, this does not result in claims about hypercomputationbut rather raises the significance of research which considers morerealistic models of interactive computation.

3.2 Thesis, Definition, Axioms or Theorem

Strictly speaking, Turing’s thesis is not provable, since itstates an identification between a vague and intuitive concept(computability) and a formal definition (Turing machines). Byconsequence, many have interpreted it as a thesis or as a definition.Alonzo Church very clearly insisted that any such identificationshould be understood as a definition. Emil Post, in contrast, spoke ofa hypothesis and, ultimately, a natural law. Stephen C. Kleene thenwas the first to use the notion of thesis to accommodate bothChurch’s and Post’s interpretations (Kleene 1943).

Clearly, the thesis would be refuted if one would be able to providean intuitively acceptable effective procedure for a task that is notTuring-computable. This far, no such counterexample has been found.Other independently defined notions of computability based onalternative foundations, such asrecursive functions have also been shown to be extensionally equivalent to Turingcomputability. These equivalences between quite different formulationsindicate that there is a natural and robust notion of computabilityunderlying our understanding. Given this apparent robustness of ournotion of computability, some have proposed to avoid the notion of athesis altogether and instead propose a set of axioms used to sharpenthe informal notion. There are several approaches, most notably, anapproach of structural axiomatization where computability itself isaxiomatized (Sieg 2008) and one whereby an axiomatization is givenfrom which the Church-Turing thesis can be derived (Dershowitz &Gurevich 2008).

4. Alternative Historical Models of Computability

Besides the Turing machine, several other models were introducedindependently of Turing in the context of research into the foundationof mathematics which resulted in theses that are logically equivalentto Turing’s thesis. For each of these models it was proven thatthey capture the Turing computable functions. Note that thedevelopment of the modern computer stimulated the development of othermodels such as register machines or Markov algorithms. More recently,computational approaches in disciplines such as biology or physics,resulted in bio-inspired and physics-inspired models such as Petrinets or quantum Turing machines. A discussion of such models, however,lies beyond the scope of this entry.

4.1 General Recursive Functions

The original formulation of generalrecursive functions can be found in Gödel 1934, which built on a suggestion byHerbrand. In Kleene 1936 a simpler definition was given and in Kleene1943 the standard form which uses the so-called minimization or\(\mu\)-operator was introduced. For more information, see the entryonrecursive functions.

Church used the definition of general recursive functions to state histhesis:

Church’s thesis Every effectively calculablefunction is general recursive

In the context of recursive function one uses the notion of recursivesolvability and unsolvability rather than Turing computability anduncomputability. This terminology is due to Post (1944).

4.2 λ-Definability

Church’s λ-calculus has its origin in the papers (Church1932, 1933) where he aimed for a logical foundation of mathematics. Itwas Church’s conviction at that time that this different formalapproach might avoid Gödel incompleteness (Sieg 1997: 177).However, the logical system proposed by Church was proven inconsistentby his two PhD students Stephen C. Kleene and Barkley Rosser and sothey started to focus on a subpart of that logic which was basicallythe λ-calculus. Church, Kleene and Rosser started toλ-define any calculable function they could think of and quitesoon Church proposed to define effective calculability in terms ofλ-definability. However, it was only after Church, Kleene andRosser had established that general recursiveness andλ-definability are equivalent that Church announced his thesispublicly and in terms of general recursive functions rather thanλ-definability (Davis 1982; Sieg 1997). See the supplement onThe λ-Calculus and Type Theory to the entry onAlonzo Church.

Today, λ-calculus is considered to be a basic model in thetheory of programming.

4.3 Post Production Systems

Around 1920–21 Emil Post developed different but related typesof production systems in order to develop a syntactical form whichwould allow him to tackle the decision problem for first-order logic.One of these forms are Post canonical systemsC which becamelater known as Post production systems.

A canonical system consists of a finite alphabet \(\Sigma\), a finiteset of initial words \(W_{0,0}\), \(W_{0,1}\),…, \(W_{0,n}\)and a finite set of production rules of the following form:

The symbolsg are a kind of metasymbols: they correspond toactual sequences of letters in actual productions. The symbolsP are the operational variables and so can represent anysequence of letters in a production. So, for instance, consider aproduction system over the alphabet \(\Sigma = \{a,b\}\) with initialword:

and the following production rule:

Then, starting with \(W_0\), there are three possible ways to applythe production rule and in each application the variables \(P_{1,i}\)will have different values but the values of the g’s are fixed.Any set of finite sequences of words that can be produced by acanonical system is called acanonical set.

A special class of canonical forms defined by Post are normal systems.A normal systemN consists of a finite alphabet \(\Sigma\),one initial word \(W_0 \in \Sigma^{\ast}\) and a finite set ofproduction rules, each of the following form:

Any set of finite sequences of words that can be produced by a normalsystem is called anormal set. Post was able to show that forany canonical setC over some alphabet \(\Sigma\) there is anormal setN over an alphabet \(\Delta\) with \(\Sigma\subseteq \Delta\) such that \(C = N \cap \Sigma^{\ast}\). It was hisconviction that (1) any set of finite sequences that can be generatedby finite means can be generated by canonical systems and (2) theproof that for every canonical set there is a normal set whichcontains it, which resulted in Post’s thesis I:

Post’s thesis I (Davis 1982) Every set offinite sequences of letters that can be generated by finite processescan also be generated by normal systems. More particularly, any set ofwords on an alphabet \(\Sigma\) which can be generated by a finiteprocess is of the form \(N \cap \Sigma^{\ast}\), withN anormal set.

Post realized that “[for the thesis to obtain its fullgenerality] a complete analysis would have to be made of all thepossible ways in which the human mind could set up finite processesfor generating sequences” (Post 1965: 408) and it is quiteprobable that the formulation 1 given in Post 1936 and which is almostidentical to Turing’s machines is the result of such ananalysis.

Post production systems became important formal devices in computerscience and, more particularly, formal language theory (Davis 1989;Pullum 2011).

4.4 Formulation 1

In 1936 Post published a short note from which one can derivePost’s second thesis (De Mol 2013):

Post’s thesis II Solvability of a problem inthe intuitive sense coincides with solvability by formulation 1

Formulation 1 is very similar to Turing machines but the‘program’ is given as a list of directions which a humanworker needs to follow. Instead of a one-way infinite tape,Post’s ‘machine’ consists of a two-way infinitesymbol space divided into boxes. The idea is that a worker is workingin this symbol space, being capable of a set of five primitive acts(\(O_{1}\) mark a box, \(O_{2}\) unmark a box, \(O_{3}\) move one boxto the left, \(O_{4}\) move one box to the right, \(O_{5}\)determining whether the box he is in is marked or unmarked), followinga finite set of directions \(d_{1}\),…, \(d_{n}\) where eachdirection \(d_{i}\) always has one of the following forms:

1. Perform one of the operations (\(O_{1}\)–\(O_4\)) and go toinstruction \(d_{j}\)
2. Perform operation \(O_{5}\) and according as the box the worker isin is marked or unmarked follow direction \(d_{j'}\) or\(d_{j''}\).
3. Stop.

Post also defined a specific terminology for his formulation 1 inorder to define the solvability of a problem in terms of formulation1. These notions are applicability, finite-1-process, 1-solution and1-given. Roughly speaking these notions assure that a decision problemis solvable with formulation 1 on the condition that the solutiongiven in the formalism always terminates with a correct solution.

5. Impact of Turing Machines on Computer Science

Turing is today one of the most celebrated figures of computerscience. Many consider him as the father of computer science and thefact that the main award in the computer science community is calledthe Turing award is a clear indication of that (Daylight 2015). Thiswas strengthened by the Turing centenary celebrations from 2012, whichwere largely coordinated by S. Barry Cooper. This resulted not only inan enormous number of scientific events around Turing but also anumber of initiatives that brought the idea of Turing as the father ofcomputer science also to the broader public (Bullynck, Daylight, &De Mol 2015). Amongst Turing’s contributions which are todayconsidered as pioneering, the 1936 paper on Turing machines stands outas the one which has the largest impact on computer science. However,recent historical research shows also that one should treat the impactof Turing machines with great care and that one should be careful inretrofitting the past into the present.

5.1 Impact on Theoretical Computer Science

Today, the Turing machine and its theory are part of the theoreticalfoundations of computer science. It is a standard reference inresearch on foundational questions such as:

• What is an algorithm?
• What is a computation?
• What is a physical computation?
• What is an efficient computation?
• etc.

It is also one of the main models for research into a broad range ofsubdisciplines in theoretical computer science such as: variant andminimal models of computability, higher-order computability,computational complexity theory, algorithmic information theory, etc. This significance of the Turingmachine model for theoretical computer science has at least twohistorical roots.

First of all, there is the continuation of the work in mathematicallogic from the 1920s and 1930s by people like Martin Davis—whowas a student of Post and Church—and Kleene. Within thattradition, Turing’s work was of course well-known and the Turingmachine was considered as the best model of computability given. BothDavis and Kleene published a book in the 1950s on these topics (Kleene1952; Davis 1958) which soon became standard references not just forearly computability theory but also for more theoretical reflectionsin the late 1950s and 1960s on computing.

Secondly, one sees that in the 1950s there is a need for theoreticalmodels to reflect on the new computing machines, their abilities andlimitations and this in a more systematic manner. It is in thatcontext that the theoretical work already done was picked up. Oneimportant development is automata theory in which one can situate,amongst others, the development of other machine models like theregister machine model or the WangB machine model which are,ultimately, rooted in Turing’s and Post’s machines; thereare the minimal machine designs discussed inSection 5.2; and there is the use of Turing machines in the context of what wouldbecome the origins of formal language theory, viz the study ofdifferent classes of machines with respect to the different“languages” they can recognize and so also theirlimitations and strengths. It are these more theoretical developmentsthat contributed to the establishment ofcomputational complexity theory in the 1960s. Of course, besides Turing machines, other models alsoplayed and play an important role in these developments. Still, withintheoretical computer science it is mostly the Turing machine whichremains thé model, even today. Indeed, when in 1965 one of thefounding papers of computational complexity theory (Hartmanis &Stearns 1965) is published, it is the multitape Turing machine whichwas introduced as the standard model for the computer.

5.2 Turing Machines and the Modern Computer

In several accounts, Turing has been identified not just as the fatherof computer science but as the father of the modern computer. Theclassical story for this more or less goes as follows: the blueprintof the modern computer can be found in von Neumann’s EDVACdesign and today classical computers are usually described as having aso-called von Neumann architecture. One fundamental idea of the EDVACdesign is the so-called stored-program idea. Roughly speaking thismeans the storage of instructions and data in the same memory allowingthe manipulation of programs as data. There are good reasons forassuming that von Neumann knew the main results of Turing’spaper (Davis 1988, Haigh and Priestley 2020). Thus, one could arguethat the stored-program concept originates in Turing’s notion ofthe universal Turing machine and, singling this out as the definingfeature of the modern computer, some might claim that Turing is thefather of the modern computer. Another related argument is that Turingwas the first who “captured” the idea of a general-purposemachine through his notion of the universal machine and that in thissense he also “invented” the modern computer (Copeland& Proudfoot 2011). This argument is then strengthened by the factthat Turing was also involved with the construction of an importantclass of computing devices (the Bombe) used for decrypting the GermanEnigma code and later proposed the design of the ACE (AutomaticComputing Engine) which was explicitly identified as a kind ofphysical realization of the universal machine by Turing himself:

Some years ago I was researching on what might now be described as aninvestigation of the theoretical possibilities and limitations ofdigital computing machines. […] Machines such as the ACE may beregarded as practical versions of this same type of machine. (Turing1947)

Note however that Turing already knew the ENIAC and EDVAC designs, twoof the earliest modern computers, and proposed the ACE as a kind ofimprovement on that design (amongst others, it had a simpler hardwarearchitecture).

These claims about Turing as the inventor and/or father of thecomputer have been scrutinized by some historians of computing(Daylight 2014; Haigh 2013; Haigh 2014; Mounier-Kuhn 2012), mostly inthe wake of the Turing centenary and this from several perspectives.Based on that research it is clear that claims about Turing being theinventor of the modern computer give a distorted and biased picture ofthe development of the modern computer. At best, he is one of the manywho made a contribution to one of the several historical developments(scientific, political, technological, social and industrial) whichresulted, ultimately, in (our concept of) the modern computer. Indeed,the “first” computers are the result of a wide number ofinnovations and so are rooted in the work of not just one but severalpeople with diverse backgrounds and viewpoints.

In the 1950s then the (universal) Turing machine starts to become anaccepted model in relation to actual computers and is used as amathematical tool to reflect on the limits and potentials ofgeneral-purpose computers by both engineers, mathematicians andlogicians. More particularly, with respect to machine designs, theuniversal machine concept provided a mathematical basis for theinsight from practice that only a few number of operations wererequired to built a general-purpose machine. This inspired in the1950s reflections on minimal machine architectures. Frankel, who(partially) constructed the MINAC stated this as follows:

One remarkable result of Turing’s investigation is that he wasable to describe a single computer which is able to computeany computable number. He called this machine auniversalcomputer. It is thus the “best possible” computermentioned.

[…] This surprising result shows that in examining the questionof what problems are, in principle, solvable by computing machines, wedo not need to consider an infinite series of computers of greater andgreater complexity but may think only of a single machine.

Even more surprising than the theoretical possibility of such a“best possible” computer is the fact that it need not bevery complex. The description given by Turing of a universal computeris not unique. Many computers, some of quite modest complexity,satisfy the requirements for a universal computer. (Frankel 1956:635)

The result was a series of experimental machines such as the MINAC,TX-0 (Lincoln Lab) or the ZERO machine (van der Poel) which in theirturn became predecessors of a number of commercial machines. It isworth pointing out that also Turing’s ACE machine design fitsinto this philosophy. It was also commercialized as the BENDIX G15machine (De Mol, Bullynck, & Daylight 2018).

Of course, by minimizing the machine instructions, coding orprogramming became a much more complicated task. To put it inTuring’s words who clearly realized this trade-off between codeand (hard-wired) instructions when designing the ACE: “[W]e haveoften simplified the circuit at the expense of the code” (Turing1947). And indeed, one sees that with these early minimal designs,much effort goes into developing more efficient coding strategies. Itis here that one can also situate one historical root of making theconnection between the universal Turing machine and the importantprinciple of the interchangeability between hardware and programs.

Today, the universal Turing machine is by many still considered as themain theoretical model of the modern computer especially in relationto the so-called von Neumann architecture. Of course, other modelshave been introduced for other architectures such as the Bulksynchronous parallel model for parallel machines or the persistentTuring machine for modeling interactive problems.

5.3 Theories of Programming

The idea that any general-purpose machine can, in principle, bemodeled as a universal Turing machine also became an importantprinciple in the context of automatic programming in the later 1950sand early 1960s. In the machine design context it was the minimizingof the machine instructions that was the most important consequence ofthat viewpoint. In the programming context then it was about the ideathat one can built a machine that is able to‘mimic’’ the behavior of any other machine and so,ultimately, the interchangeability between machine hardware andlanguage implementations. This is introduced in several forms in thelater 1950s by people like John W. Carr III and Saul Gorn—whowere also actively involved in the shaping of theAssociation forComputing Machinery (ACM)—as the unifying theoretical ideafor automatic programming which indeed is about the (automatic)“translation” of higher-order to lower-level, and,ultimately, machine code. Thus, also in the context of programming,the universal Turing machine started to take on its foundational rolein the 1950s (Daylight 2015).

Whereas the Turing machine is and was a fundamental theoretical modeldelimiting what is possible and not on the general level, it did nothave a real impact on the syntax and semantics of programminglanguages. In that context it were rather λ-calculus and Postproduction systems that had an effect (though also here one should becareful in overstating the influence of a formal model on aprogramming practice). In fact, Turing machines were often regarded asmachine models rather than as a model for programming:

Turing machines are not conceptually different from the automaticcomputers in general use, but they are very poor in their controlstructure. […] Of course, most of the theory of computabilitydeals with questions which are not concerned with the particular wayscomputations are represented. It is sufficient that computablefunctions be represented somehow by symbolic expressions, e.g.,numbers, and that functions computable in terms of given functions besomehow represented by expressions computable in terms of theexpressions representing the original functions. However, a practicaltheory of computation must be applicable to particular algorithms.(McCarthy 1963: 37)

Thus one sees that the role of the Turing machine for computer scienceshould be situated rather on the theoretical level: the universalmachine is today by many still considered as the model for the moderncomputer while its ability to mimic machines through its manipulationof programs-as-data is one of the basic principles of moderncomputing. Moreover, its robustness as a model of computability havemade it the main model to challenge if one is attacking versions ofthe so-called (physical) Church-Turing thesis.

Bibliography

• Barwise, Jon and John Etchemendy, 1993,Turing’sWorld, Stanford, CA: CSLI Publications.
• Boolos, George S. and Richard C. Jeffrey, 1974,Computabilityand Logic, Cambridge: Cambridge University Press; fifth edition2007. doi:10.1017/CBO9780511804076 (fifth edition)
• Bromley, Allan G., 1985, “Stored Program Concept. The Originof the Stored Program Concept”, Technical Report 274, BasserDepartment of Computer Science, November 1985. [Bromley 1985 available online]
• Bullynck, Maarten, Edgar G. Daylight, and Liesbeth De Mol, 2015,“Why Did Computer Science Make a Hero Out of Turing?”,Communications of the ACM, 58(3):37–39.doi:10.1145/2658985
• Church, Alonzo, 1932, “A Set of Postulates for theFoundation of Logic”,Annals of Mathematics, 33(2):346–366. doi:10.2307/1968337
• –––, 1933, “A Set of Postulates for theFoundation of Logic (Second Paper)”,Annals ofMathematics, 34(4): 839–864. doi:10.2307/1968702
• –––, 1936a, “An Unsolvable Problem ofElementary Number Theory”,American Journal ofMathematics, 58(2): 345–363.
• –––, 1936b, “A Note on theEntscheidungsproblem”,Journal of Symbolic Logic, 1(1):40–41. doi:10.2307/2269326
• –––, 1937, “Review of: On ComputableNumbers with An Application to the Entscheidungsproblem by A.M.Turing”,Journal of Symbolic Logic, 2(1): 42–43.doi:10.1017/S002248120003958X
• Cook, Matthew, 2004, “Universality in Elementary CellularAutomata”,Complex Systems, 15(1): 1–40.
• Cooper, S. Barry and Jan Van Leeuwen, 2013,Alan Turing: HisWork and Impact, Amsterdam: Elsevier.doi:10.1016/C2010-0-66380-2
• Copeland, B. Jack, 2002, “Accelerating TuringMachines”,Minds and Machines, 12(2): 281–301.doi:10.1023/A:1015607401307
• Copeland, B. Jack and Diane Proudfoot, 2011, “Alan Turing:Father of the Modern Computer”,The Rutherford Journal,4: 1. [Copeland & Proudfoot 2011 available online]
• Davis, Martin, 1958 [1982],Computability andUnsolvability, New York: McGraw-Hill. Reprinted Dover, 1982.
• –––, 1965,The Undecidable. Basic papers onundecidable propositions, unsolvable problems and computablefunctions, New York: Raven Press.
• –––, 1978, “What is a Computation?”,Lynn Arthur Steen (ed.),Mathematics Today: Twelve InformalEssays, New York: Springer, pp. 241–267.doi:10.1007/978-1-4613-9435-8_10
• –––, 1982, “Why Gödel Didn’tHave Church’s Thesis”,Information and Control,54:(1–2): 3–24. doi:10.1016/S0019-9958(82)91226-8
• –––, 1988, “Mathematical Logic and theOrigin of the Modern Computer”, in Herken 1988:149–174.
• –––, 1989, “Emil Post’s Contributionto Computer Science”,Proceedings of the Fourth AnnualSymposium on Logic in Computer Science, IEEE Computer SocietyPress, pp. 134–137. doi:10.1109/LICS.1989.39167
• Davis, Martin and Wilfried Sieg, 2015, “ConceptualConfluence in 1936: Post and Turing”, in Giovanni Sommaruga andThomas Strahm (eds.),Turing’s Revolution: The Impact of HisIdeas about Computability, Cham: Springer.doi:10.1007/978-3-319-22156-4_1
• Daylight, Edgar G., 2014, “A Turing Tale”,Communications of the ACM, 57(10): 36–38.doi:10.1145/2629499
• –––, 2021, “The Halting Problem andSecurity’s Language-Theoretic Approach: Praise and CriticismFrom a Technical Historian”,Computability, 10(2):141–158.
• –––, 2015, “Towards a Historical Notion of‘Turing—The Father of Computer Science’”,History and Philosophy of Logic, . 36(3): 205–228.doi:10.1080/01445340.2015.1082050
• De Mol, Liesbeth, 2013, “Generating, Solving and theMathematics of Homo Sapiens. Emil Post’s Views Oncomputation”, Hector Zenil (ed.),A Computable Universe.Understanding Computation & Exploring Nature As Computation,Hackensack, NJ: World Scientific, pp. 45–62.doi:10.1142/9789814374309_0003 [De Mol 2013 available online]
• De Mol, Liesbeth, Maarten Bullynck, and Edgar G. Daylight, 2018,“Less is More in the Fifties: Encounters between LogicalMinimalism and Computer Design during the 1950s”,IEEEAnnals of the History of Computing, 40(1): 19–45.doi:10.1109/MAHC.2018.012171265 [De Mol et al. 2018 available online]
• Deutsch, D., 1985, “Quantum Theory, the Church-TuringPrinciple and the Universal Quantum Computer”,Proceedingsof the Royal Society A, 400(1818): 97–117.doi:10.1098/rspa.1985.0070
• Dershowitz, Nachum and Yuri Gurevich, 2008, “ A NaturalAxiomatization of Computability and Proof of Church’sThesis”,Bulletin of Symbolic Logic, 14(3):299–350.
• Frankel, Stanley, 1956, “Useful Applications of aMagnetic-Drum Computer”,Electrical Engineering, 75(7):634–39, doi:10.1109/EE.1956.6442018
• Gandy, Robin, 1980, “Church’s Thesis and Principlesfor Mechanism”, in Jon Barwise, H. Jerome Keisler, and KennethKunen (eds.),The Kleene Symposium: Proceedings of the SymposiumHeld June 18–24, 1978 at Madison, Wisconsin, U.S.A.,(Studies in Logic and the Foundations of Mathematics, 101), Amsterdam:North-Holland, pp. 123–148.doi:10.1016/S0049-237X(08)71257-6
• –––, 1988, “The Confluence of Ideas in1936”, in Herken 1988: 55–111.
• Gödel, Kurt, 1929, “Die Vollständigkeit der Axiomedes logischen Funktionenkalkül”,Monatshefte fürMathematik und Physik, 37: 349–360.doi:10.1007/BF01696781
• –––, 1934, “On Undecidable Propositions ofFormal Mathematical Systems”, mimeographed lecture notes by S.C. Kleene and J. B. Rosser, Institute for Advanced Study, Princeton,NJ; corrected and amplified in Davis 1965: 41–74.
• Goldin, Dina, 2000, “Persistent Turing Machines as a Modelof Interactive Computation”,International Symposium onFoundations of Information and Knowledge Systems (Lecture Notesin Computer Science: 1762), Berlin: Springer, pp. 116–135.
• Grier, David Alan, 2007,When Computers Were Human,Princeton, NJ: Princeton University Press.
• Haigh, Thomas, 2013, “‘Stored Program Concept’Considered Harmful: History and Historiography”, in PaolaBonizzoni, Vasco Brattka, and Benedikt Löwe,The Nature ofComputation. Logic, Algorithms, Applications: 9th Conference onComputability in Europe, CiE 2013, Milan, Italy, July 1–5, 2013Proceedings, (Lecture Notes in Computer Science, 7921), Berlin:Springer, pp. 241–251. doi:10.1007/978-3-642-39053-1_28
• –––, 2014, “Actually, Turing Did NotInvent the Computer”,Communications of the ACM, 57(1):36–41. doi:10.1145/2542504
• Haigh, Thomas and Mark Priestley, 2020, “Von Neumann ThoughtTuring’s Universal Machine was ‘Simple and Neat’:But That Didn’t Tell Him How to Design a Computer”,Communications of the ACM, 63(1): 26–32.
• Hamkins, Joel David and Andy Lewis, 2000, “Infinite TimeTuring Machines”,Journal of Symbolic Logic, 65(2):567–604. doi:10.2307/2586556
• Hartmanis, J. and R.E. Stearns, 1965, “On the ComputationalComplexity of Algorithms”Transactions of the AmericanMathematical Society, 117: 285–306.doi:10.1090/S0002-9947-1965-0170805-7
• Herken, Rolf, (ed.), 1988,The Universal Turing Machine: AHalf-Century Survey, New York: Oxford University Press.
• Hilbert, David, 1930, “Naturerkennen und Logik”,Naturwissenschaften, 18(47–49): 959–963.doi:10.1007/BF01492194
• Hilbert, David and Wilhelm Ackermann, 1928,Grundzüge derTheoretischen Logik, Berlin: Springer.doi:10.1007/978-3-642-65400-8
• Hodges, Andrew, 1983,Alan Turing: The Enigma, New York:Simon and Schuster.
• Kleene, Stephen Cole, 1936, “General Recursive Functions ofNatural Numbers”,Mathematische Annalen, 112:727–742. doi:10.1007/BF01565439
• –––, 1943, “Recursive predicates andquantifiers”,Transactions of the American MathematicalSociety, 53(1): 41–73. doi:10.2307/2267986
• –––, 1952,Introduction toMetamathematics, Amsterdam: North Holland.
• Lambek, Joachim, 1961, “How to Program an InfiniteAbacus”,Canadian Mathematical Bulletin, 4:295–302. doi:10.4153/CMB-1961-032-6
• Lassègue, Jean, and Giuseppe Longo, 2012, “What isTuring’s Comparison between Mechanism and Writing Worth?”,in Barry Cooper, et al. (eds.),How the World Computes. CiE2012 (Lecture Notes in Computer Science: 7318), Berlin,Heidelberg: Springer, pp. 450–461.
• Lewis, Henry R. and Christos H. Papadimitriou, 1981,Elementsof the Theory of Computation, Englewood Cliffs, NJ:Prentice-Hall.
• Lin, Shen and Tibor Radó, 1965, “Computer Studies ofTuring Machine Problems”,Journal of the Association forComputing Machinery, 12(2): 196–212.doi:10.1145/321264.321270
• Mancosu, Paolo, Richard Zach, and Calixto Badesa, 2009, “TheDevelopment of Mathematical Logic from Russell to Tarski,1900–1935”, in Leila Haaparanta (ed.),The Developmentof Modern Logic, New York: Oxford University Press, pp.318–470. doi:10.1093/acprof:oso/9780195137316.003.0029 [Mancosu et al. 2009 available online]
• Margenstern, Maurice, 2000, “Frontier Between Decidabilityand Undecidability: A Survey”,Theoretical ComputerScience, 231(2): 217–251.doi:10.1016/S0304-3975(99)00102-4
• Martin, Alice; Magnaudet, Mathieu; Conversy, Spéphanie,2023, “Computers as Interactive Machines: Can We Build anExplanatory Abstraction?”,Minds and Machines, 33(1):83–112.
• Martini, Simone, 2020, “The Standard Model for ProgrammingLanguages: The Birth of a Mathematical Theory of Computation”,in Frank S. de Boer and Jacopo Mauro (eds.),Developments in theDesign and Implementation of Programming Languages (Open AccessSeries in Informatics), Schloss Dagstuhl: Leibniz-Zentrum fürInformatik, Article No. 8: 8:1–8:13. [Martini 2020 available online]
• McCarthy, John, 1963, “A Basis for a Mathematical Theory ofComputation”, in: P. Braffort and D. Hirschberg,ComputerProgramming and Formal Systems, Amsterdam: North-Holland, pp.33–70. [McCarthy 1963 available online]
• Mélès, Baptiste, 2020/21. “Les langages deTuring”, inIntellectica. Revue de l’Association pourla Recherche Cognitive, 72: 81–110.
• Minsky, Marvin, 1961, “Recursive Unsolvability ofPost’s Problem of ‘Tag’ and other Topics in Theoryof Turing Machines”,Annals of Mathematics, 74(3):437–455. doi:10.2307/2269716
• –––, 1967,Computation: Finite and InfiniteMachines, Englewood Cliffs, NJ: Prentice Hall.
• Moore, E.F., 1952, “A simplified universal Turingmachine”,Proceedings of the Association of ComputingMachinery (meetings at Toronto, Ontario), Washington, DC: SaulsLithograph, 50–55. doi:10.1145/800259.808993
• Mounier-Kuhn, Pierre, 2012, “Logic and Computing in France:A Late Convergence”, inAISB/IACAP World Congress 2012:History and Philosophy of Programming, University of Birmingham,2–6 July 2012. [Mounier-Kuhn 2012 available online]
• Odifreddi, P., 1989,Classical Recursion Theory,Amsterdam: Elsevier.
• Petzold, Charles, 2008,The Annotated Turing: A Guided TourThrough Alan Turing’s Historic Paper on Computability and TuringMachines, Indianapolis, IN: Wiley.
• Post, Emil L., 1936, “Finite CombinatoryProcesses-Formulation 1”,Journal of Symbolic Logic,1(3): 103–105. doi:10.2307/2269031
• –––, 1944, “Recursively Enumerable Sets ofPositive Integers and Their Decision Problems”,Bulletin ofthe American Mathematical Society, 50(5): 284–316. [Post 1944 available online]
• –––, 1947, “Recursive Unsolvability of aProblem of Thue”,Journal of Symbolic Logic, 12(1):1–11. doi:10.2307/2267170
• –––, 1965, “Absolutely Unsolvable Problemsand Relatively Undecidable Propositions—Account of anAnticipation”, in Martin Davis (ed.),The Undecidable: BasicPapers on Undecidable Propositions, Unsolvable Problems and ComputableFunctions, New York: Raven Press. Corrected republication 2004,Dover publications, New York, pp. 340–433.
• Pullum, Geoffrey K., 2011, “On the Mathematical FoundationsofSyntactic Structures”,Journal of Logic,Language and Information, 20(3): 277–296.doi:10.1007/s10849-011-9139-8
• Putnam, Hilary, 1965, “Trial and Error Predicates and theSolution to a Problem of Mostowski”,The Journal of SymbolicLogic, 30(1): 49–57.
• Rabin, M.O. and D. Scott, 1959, “Finite Automata and theirDecision Problems”,IBM Journal of Research andDevelopment, 3(2): 114–125. doi:10.1147/rd.32.0114
• Radó, Tibor, 1962, “On Non-ComputableFunctions”,Bell System Technical Journal, 41(3/May):877–884. doi:10.1002/j.1538-7305.1962.tb00480.x
• Shannon, Claude E., 1956, “A Universal Turing Machine withTwo Internal States”, in Shannon & McCarthy 1956:157–165. doi:10.1515/9781400882618-007
• Shannon, Claude E. and John McCarthy (eds), 1956,AutomataStudies, (Annals of Mathematics Studies, 34), Princeton:Princeton University Press.
• Shapiro, Stewart, 2007, “Computability, Proof, andOpen-Texture”, in Adam Olszewski, Jan Wolenski, and RobertJanusz (eds.),Church’s Thesis After 70 years, Berlin:Ontos Verlag, pp. 420–455. doi:10.1515/9783110325461.420
• Sieg, Wilfried, 1994, “Mechanical Procedures andMathematical Experience”, in Alexander George (ed.),Mathematics and Mind, Oxford: Oxford University Press, pp.71–117.
• –––, 1997, “Step by Recursive Step:Church’s Analysis of Effective Calculability”,TheBulletin of Symbolic Logic, 3(2): 154–180.doi:10.2307/421012
• –––, 2008, “Church without Dogma: Axiomsfor Computability”, in S. Barry Cooper, Benedikt Löwe, andAndrea Sorbi (eds.),New Computational Paradigms: ChangingConceptions of What is Computable, New York: Springer Verlag, pp.139–152. doi:10.1007/978-0-387-68546-5_7
• Sipser, Michael, 1996,Introduction to the Theory ofComputation, Boston: PWS Publishing.
• Soare, Robert I., 1996, “Computability and Recursion”,Bulletin for Symbolic Logic, 2(3): 284–321.doi:10.2307/420992
• Strachey, Christopher, 1965, “An Impossible Program (letterto the editor )”,The Computer Journal, 7(4): 313.doi:10.1093/comjnl/7.4.313
• Teuscher, Christof (ed.), 2004,Alan Turing: Life and Legacyof a Great Thinker, Berlin: Springer.doi:10.1007/978-3-662-05642-4
• Turing, A.M., 1936–7, “On Computable Numbers, With anApplication to the Entscheidungsproblem”,Proceedings of theLondon Mathematical Society, s2–42: 230–265;correctionibid., s2–43: 544–546 (1937).doi:10.1112/plms/s2-42.1.230 and doi:10.1112/plms/s2-43.6.544
• –––, 1937, “Computability andλ-Definability”,Journal of Symbolic Logic,2(4): 153–163. doi:10.2307/2268280
• –––, 1939, “Systems of Logic Based onOrdinals”,Proceedings of the London MathematicalSociety, s2–45: 161–228.doi:10.1112/plms/s2-45.1.161
• –––, 1947 [1986], “Lecture to the LondonMathematical Society on 20 February 1947”, reprinted inA M.Turing’s ACE Report of 1946 and Other Papers: Papers by AlanTuring and Michael Woodger, (Charles Babbage Institute Reprint,10), B.E. Carpenter and R.W. Doran (eds.), Cambridge, MA: MIT Press,1986.
• –––, 1954, “Solvable and UnsolvableProblems”,Science News, (February, Penguin), 31:7–23.
• Wang, Hao, 1957, “A Variant to Turing’s Theory ofComputing Machines”,Journal of the ACM, 4(1):63–92. doi:10.1145/320856.320867
• Watanabe, Shigeru, 1961, “5-Symbol 8-State and 5-Symbol6-State Universal Turing Machines”,Journal of the ACM,8(4): 476–483. doi:10.1145/321088.321090
• Woods, Damien and Turlough Neary, 2007, “Small Semi-WeaklyUniversal Turing Machines”, in Jérôme Durand-Loseand Maurice Margenstern (eds.),Machines, Computations, andUniversality: 5th International Conference, MCU 2007 Orléans,France, September 10–13, 2007, (Lecture Notes in ComputerScience, 4664), Berlin: Springer, pp. 303–315.doi:10.1007/978-3-540-74593-8_26
• –––, 2009, “The Complexity of SmallUniversal Turing Machines: A Survey”,Theoretical ComputerScience, 410(4–5): 443–450.doi:10.1016/j.tcs.2008.09.051

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

• Aaronson, Scott, Mohammad Bavarian, Toby Cubitt, Sabee Grewal,Giulio Gueltrini, Ryan O’Donnell, Marien Raat, 2024, “Computability Theory of Closed Timelike Curves”, manuscript available at arXiv.org.
• “Turing Machines”,Stanford Encyclopedia ofPhilosophy (Fall 2018 Edition), Edward N. Zalta (ed.), URL = <http://plato.stanford.edu/archives/fall2018/entries/turing-machine/>. [This was the previous entry on Turing Machines in the SEP, writtenby David Barker-Plummer.].
• The Alan Turing Home Page, maintained by Andrew Hodges
• Bletchley Park, in the U.K., where, during the Second World War, Alan Turing wasinvolved in code breaking activities at Station X.

Busy Beaver

• Collaborative project on Busy Beavers led by Tristan Stérin.
• Michael Somos’ page of Busy Beaver references (from archive.org).

Artistic projects

• A poetic proof of the halting problem by Geoff Pullum
• Illuminated universal Turing machines, an art project by Roman Verostko, a digital art pioneer.
• Turing drawings, an art project by Maxime Chevalier-Boisvert.

The Halting Problem

• Halting problem is solvable (funny)

Online Turing Machine Simulators

Abstractly speaking, Turing machines are more powerful than any devicethat can actually be built, given the infinite availability of timeand space, but they can be simulated both in software andhardware.

Software simulators

There are many Turing machine simulators available online. Here aretwo browser-based simulators that allow you to play around, built yourown machine and store it.

• Turing machine simulator by Andy Li
• Turing machine simulator by Martin Ugarte

Hardware simulators

• Turing Machine in the Classic Style, Mike Davey’s physical Turing machine simulator.
• Lego of Doom, Turing machine simulator using Lego™.
• An analysis of the computational complexity of Gisbert Hasenjaeger’s electromechanical Turing machine. The machine was built in 1963.

Related Entries

Church, Alonzo |Church-Turing Thesis |computability and complexity |computational complexity theory |recursive functions |Turing, Alan

Acknowledgments

The version of this entry published on September 24, 2018 isessentially a new entry, though the author would like to acknowledgethe few sentences that remain from the previous version written byDavid Barker-Plummer. See also footnote 1 for an acknowledgment to S.Barry Cooper.