Winter 2012 Edition
Turing machines, first described byAlan Turing in (Turing 1937),are simple abstract computational devices intended to help investigatethe extent and limitations of what can be computed.
Turing was interested in the question of what it means for a task tobe computable, which is one of the foundational questions in thephilosophy of computer science.Intuitively a task is computable if it is possible to specify a sequence ofinstructions which will result in the completion of thetask when they are carried out by some machine. Such a set ofinstructions is called aneffective procedure,oralgorithm, for the task. The problem with this intuitionis that what counts as an effective procedure may depend on thecapabilities of the machine used to carry out the instructions. Inprinciple, devices with different capabilities may be able to completedifferent instruction sets, and therefore may result in differentclasses of computable tasks (see the entryoncomputability and complexity).
Turing proposed a class of devices that came to be known as Turingmachines. These devices lead to a formal notion of computation that wewill callTuring-computability. A task is Turing computableif it can be carried out by some Turing machine.
The proposition that Turing's notion captures exactly the intuitiveidea of effective procedure is called theChurch-Turing thesis.This proposition is not provable, since it is a claim about therelationship between a formal concept and intuition. The thesis wouldbe refuted by an intuitively acceptable algorithm for a task that isnot Turing-computable, and no such counterexample has beenfound. Other independently defined notions of computability based onalternative foundations, such asrecursive functions andabacus machines have been shown to be equivalent toTuring-computability. These two facts indicate that there is at leastsomething natural about this notion of computability.
Turing machines are not physical objects but mathematical ones. Werequire neither soldering irons nor silicon chips to build one. Thearchitecture is simply described, and the actions that may be carriedout by the machine are simple and unambiguously specified. Turingrecognized that it is not necessary to talk abouthow themachine carries out its actions, but merely to take as given the twinideas that the machine can carry out the specified actions, and thatthose actions may be uniquely described.
A Turing machine is a kind ofstate machine. At any timethe machine is in any one of a finite number of states. Instructionsfor a Turing machine consist in specified conditions under which themachine will transition between one state and another.
The literature contains a number of different definitions of Turingmachine. While differing in the specifics, they are equivalent in thesense that the same tasks turn out to be Turing-computable in everyformulation. The definition here is just one of the commondefinitions, with some variants discussed in section 3 of thisarticle.
A Turing machine has an infinite one-dimensionaltape dividedinto cells. Traditionally we think of the tape as being horizontalwith the cells arranged in a left-right orientation. The tape has oneend, at the left say, and stretches infinitely far to the right. Eachcell is able to contain one symbol, either ‘0’ or‘1’.
The machine has aread-write head which is scanning a single cell on the tape. This read-write head can move leftand right along the tape to scan successive cells.
The action of a Turing machine is determined completely by (1) thecurrent state of the machine (2) the symbol in the cell currently beingscanned by the head and (3) a table of transition rules, which serve asthe “program” for the machine.
Each transition rule is a 4-tuple:
⟨Statecurrent,Symbol,Statenext,Action ⟩
which can be read as saying “if the machine is in stateStatecurrent and the cell being scanned containsSymbol then move into stateStatenexttakingAction”. As actions, a Turingmachine may either to write a symbol on the tape in the current cell(which we will denote with the symbol in question), or to move the headone cell to the left or right, which we will denote by the symbols« and » respectively.
If the machine reaches a situation in which there is no uniquetransition rule to be carried out, i.e., there is none or more than one, then themachine halts.
In modern terms, the tape serves as the memory of the machine, whilethe read-write head is the memory bus through which data is accessed(and updated) by the machine. There are two important things to noticeabout the setup. The first concerns the definition of the machineitself, namely that the machine's tape is infinite in length. Thiscorresponds to an assumption that the memory of the machine isinfinite. The second concerns the definition of Turing-computable,namely that a function will be Turing-computable if there exists a setof instructions that will result in a Turing machine computing thefunction regardless of the amount of time it takes. One can think ofthis as assuming the availability of infinite time to complete thecomputation.
These two assumptions are intended to ensure that the definition ofcomputation that results is not too narrow. This is, it ensures thatno computable function will fail to be Turing-computable solelybecause there is insufficient time or memory to complete thecomputation. It follows that there may be some Turing-computablefunctions which may not be carried out by any existing computer,perhaps because no existing machine has sufficient memory to carry outthe task. Some Turing-computable functions may not ever be computablein practice, since they may require more memory than can be builtusing all of the (finite number of) atoms in the universe. Conversely,a result that shows that a function is not Turing-computable is verystrong, since it certainly implies that no computer that we could everbuild could carry out thecomputation.Section 5 shows that somefunctions are not Turing-computable.
Talk of “tape” and a “read-write head” is intended to aid the intution(and reveals something of the time in which Turing was writing) butplays no important role in the definition of Turing machines. Insituations where a formal analysis of Turing machines is required, itis appropriate to spell out the definition of the machinery and programin more mathematical terms. Purely formally a machine might be definedto consist of:
Acomputation state describes everything that is necessary toknow about the machine at a given moment in its execution. At anygiven step of the executions
The transition function for the machine δ is a functionfrom computation states to computation states, such that ifδ(S) =T
The transition function determines the new content of the tape byreturning a new function σ but this new function is constrainedto be very similar to the old. The first constraint above says thatthe content of the cells of the tape is that same every where exceptpossibly at the cell that was being scanned. Since Turing machines caneither change the content of a cell or move the head, then if the cellis modified, then the head must not be moved in the transition, and ifit is not modified, then the head is constrained to move at most onecell in either direction. This is the meaning of the secondconstraint above.
This definition is very similar to that given in the entry oncomputability and complexity, with the significant difference that in the alternative definition themachine may write a new symbol as well as move during anytransition. This change does not alter the set of Turing-computablefunctions, and simplifies the formal definition by removing the secondcondition on the transition function in our definition. Both formaldefinitions permit the alphabet of symbols on the tape to be any finiteset, while the original definition insisted on Σ={0,1}this change also does not impact the definition of the set ofTuring-computable functions.
Every Turing machine has the same machinery. What makes one Turingmachine perform one task and another a different task is the table oftransition rules that make up the machine's program, and a specifiedinitial state for the machine. We will assume throughout thata machine starts in the lowest numbered of its states.
We can describe a Turing machine, therefore, by specifying only the4-tuples that make up its program. Here are the tuples describing asimple machine.
⟨s0, 1,s0, » ⟩ ⟨s0, 0,s1, 1 ⟩ ⟨s1, 1,s1, « ⟩ ⟨s1, 0,s2, » ⟩
This machine has three states,numbereds0,s1 ands2. The first two instructions describe what happens instates0. There are two possibilities, either themachine is scanning a ‘1’, in which case the head moves tothe right and stays in states0. The machine leavesstates0 and enterss1 if it isscanning a ‘0’. It writes a ‘1’ on thattransition. The second two instructions describe what happens instates1, namely if it is scanning a‘1’ the machine moves the head to the left staying instates1. If it is scanning a ‘0’, thehead moves to the right and the machine moves intostates2. Since there are no instructions forstates2, the machine halts if it reaches thatstate.
When we are interested in examining the behaviour of a Turing machine, it is common and perhaps more perspicuous to represent the machine using a state diagram. Here is the machine represented in this format.
Figure 1: A State Diagram
In this figure, states are represented by the circles, with theunique double circle being the initial state. A transition isrepresented as an arrow originating from one circle and landing atanother (possibly the same) circle. The arrows are labeled by a pairconsisting first of the symbol that must be being scanned for the arrowto be followed, and second the action that is to be taken as thetransition is made. The action will either be the symbol to be written,or « or » indicating a move to the left or right.
In what follows we will describe Turing machines in the statemachine format.
In order to speak about a Turing machine that does something useful,we will have to provide an interpretation of the symbols recorded onthe tape. For example, if we want to design a machine which willperform some mathematical function, addition say, then we will need todescribe how to interpret the ones and zeros appearing on the tape asnumbers.
In the examples that follow we will represent the numbernas a block ofn+1 copies of the symbol ‘1’ on the tape. Thuswe will represent the number 0 as a single ‘1’ and the number 3 as ablock of four ‘1’s.
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 a singleoccurrence of the symbol ‘0’. For example, to compute thesum 3+4, a Turing machine will start in the following configuration,where the ellipses indicate that the tape has only zeros on the cellsthat we can't see, and the upward arrow indicates the cell that iscurrently scanned.
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 4 ‘1’s, representing the number3, and the second contains 5 ‘1’s, representing the number4.
A machine must finish in standard configuration too. There must be asingle block of ‘1’s on the tape, and the machine must bescanning the leftmost such ‘1’. If the machine correctlycomputes the function then this block must represent the correctanswer. So an addition machine started in the configuration above mustfinish on a tape that looks like this:
Adopting this convention for the terminating configuration of aTuring machine means that we can compose machines by identifying thefinal state of one machine with the initial state of the next.
Under these conventions, the state diagram inFigure 1 describes a machine which computes the successor (add-one)function. That is when started in standard configuration on a taperepresenting the numbern it will halt in standardconfiguration representing the numbern+1. It does this byusing state s0 to scan to the first ‘0’ to theright of the (single) block of ‘1’s. It then replaces that‘0’ by a ‘1’, and scans left in states1 until a ‘0’ is found (this is the first zeroto the left of the block of ‘1’s). It then moves back to scanthe first ‘1’ and halts in states2.
Above, we see the initial state. Click on the image to see a movieof the execution of the machine. (Click again to stop and reset.)
For another example, consider the machine in Figure 2 which computesthe addition function. That is, when started on a standard taperepresenting the numbersn andm, the machine haltson a tape representingn+m.
Figure 2: A Machine for Computingn+m
Since the tape initially contains at least two ‘1’s andwe write one more, the deletion of two ‘1’s will leave atleast one on the tape at the end of the computation, and we will bescanning the leftmost of them.
Recall that we said that an execution state of a Turing machine may bedescribed by the name of the state that the machine isinQs, the symbols on the tape,σs, and the cell that is currently beingscannedhs. We will represent such a descriptionusing a figure like that in Figure 3, in which the arrow representsthe currently scanned cell and the name of the current state iswritten below the arrow.
Figure 3: The Instantaneous Description of a Turing MachineComputation
This indicates that out Turing machine is instates4, scanning the indicated cell of the tape.The tape is assumed to contain ‘0’s everywhere that is notvisible.
We have presented here one of the most common formulations of Turing'sbasic idea. There are a number of variations to the formulation thatturn out to be equivalent to this one, and different authors presentTuring machines using any of these. Since they are all provablyequivalent to one another we can consider any of the formulations asbeing the definition of Turing machine as we find convenient.
FormulationF1 and formulationF2 are equivalent if for every machinedescribed in formulationF1 there is machine adescribed inF2 which has the same input-outputbehavior, and vice versa, i.e., when started on the same tape at thesame cell, will terminate with the same tape on the same cell.
Two-way infinite tapes
In our original formulation we specified that the tape had an end, atthe left say, and stretched infinitely far to the right. Relaxing thisstipulation to allow the tape to stretch infinitely far to right andleft results in a new formulation of Turing machines. You might expectthat the additional flexibility of having a two-way infinite tapewould increase the number of functions that could be computed, but itdoes not. If there is a machine with a two-way infinite tape forcomputing some function, there there is machine with a one-wayinfinite tape that will compute that same function.
Arbitrary numbers of read-write heads
Modifying the definition of a Turing machine so that the machine hasseveral read-write heads does not alter the notion ofTuring-computability.
Multiple tapes
Instead of a single infinite tape, we could consider machinespossessing many such tapes. The formulation of such a machine wouldhave to allow the tuples to specify which tape is to be scanned,where the new symbol is to be written, and which tape head is tomove. Again this formulation is equivalent to the original.
Two-dimensional tapes
Instead of a one-dimensional infinite tape, we could consider atwo-dimensional “tape”, which stretches infinitely far upand down as well as left and right. We would add to the formulationthat a machine transition can cause the read-write head to move up ordown one cell in addition to being able to move left and right. Againthis formulation is equivalent to the original.
Arbitrary movement of the head
Modifying the definition of a Turing machine so that the read-writehead may move an arbitrary number of cells at any given transition doesnot alter the notion of Turing-computability.
Arbitrary finite alphabet
In our original formulation we allowed the use of only two symbols onthe tape. In fact we do not increase the power of Turing machines byallowing the use of any finite alphabet of symbols.
5-tuple formulation
A common way to describe Turing machines is to allow the machine toboth write and move its head in the same transition. This formulationrequires the 4-tuples of the original formulation to be replaced by5-tuples
⟨State0,Symbol,Statenew,Symbolnew,Move ⟩
whereSymbolnew is the symbol written,andMove is one of « and ».
Again, this additional freedom does not result in a new definitionof Turing-computable. For every one of the new machines there is one ofthe old machines with the same properties.
Non-deterministic Turing machines
An apparently more radical reformulation of the notion of Turingmachine allows the machine to explore alternatives computations inparallel. In the original formulation we said that if the machinespecified multiple transitions for a given state/symbol pair, and themachine was in such a state then it would halt. In this reformulation,all transitions are taken, and all the resulting computationsare continued in parallel. One way to visualize this is that themachine spawns an exact copy of itself and the tape for eachalternative available transition, and each machine continues thecomputation. If any of the machines terminates successfully, then theentire computation terminates and inherits that machine's resultingtape. Notice the word successfully in the preceding sentence. In thisformulation, some states are designated asaccepting statesand when the machine terminates in one of these states, then thecomputation is successful, otherwise the computation is unsuccessfuland any other machines continue in their search for a successfuloutcome.
The addition of non-determinism to Turing machines does not alterthe definition of Turing-computable.
Turing's original formulation of Turing Machines used the 5-tuplerepresentation of machines. Post introduced the 4-tuple representation,and the use of a two-way infinite tape.
A more complex machine
In addition to performing numerical functions using unaryrepresentation for numbers, we can perform tasks such as copyingblocks of symbols, erasing blocks of symbols and so on. Here is anexample of a Turing machine which when started in standardconfiguration on a tape containing a single block of ‘1’s,halts on a tape containing two copies of that block of‘1’s, with the blocks separated by a single‘0’. It uses an alphabet consisting of the symbols‘0’, ‘1’ and ‘A’.
Figure 4: A Machine for Copying a Block of1s
The action of this machine is to repeatedly change one of the original‘1’s into an A, and then write a new ‘1’ to the right ofall remaining ‘1’ on the tape, after leaving a zerobetween the original block and the copy. When we run out of theoriginal ‘1’s, we turn the As back into ‘1’s.
The initial state,s0, is used to change a‘1’ into an ‘A’, and move to the right andinto states1. In states1 weskip the remainder of the block of ‘1’s until we find a‘0’ (the block separator) and ins2 weskip any ‘1’s to the right of that ‘0’ (thisis the copy of the block of ‘1’s that we aremaking). When we reach the end of that block, we find a‘0’, which we turn into a ‘1’ and head back tothe left, and into states3. Statess3 ands4 skip leftward overthe ‘1’s and separating ‘0’ on the tape untilan ‘A’ is found. When this occurs, we go back into states0, and move rightward.
At this point, we are either scanning the next ‘1’ of theoriginal block, or the original block has all been turned into‘A's, and we are scanning the separator ‘0’. In theformer case, we make another trip through statess1–s4, but in the latter, wemove into states5, moving leftward. In thisstate we will repeatedly find ‘A's, which we replace with‘1’s, and move to the left. If we find a ‘0’,then all of the ‘A's have been turned back into‘1’s. We will be scanning the ‘0’ to the leftof the original cell, and so we move right, and into the final states6.
This copying machine could be used in conjunction with the additionmachine ofFigure 2 to construct a doubling machine, i.e., a machine which, when startedon a tape representing the numbern halts on a taperepresenting2n. We could do this by first using the copyingmachine to produce a tape with two copies ofn on the tape,and then using the addition machine to computen+n(=2n). We would do this by identifying the copying machine'shalt state (s6) with the adding machine's initialstate (s0).
The construction just suggested relies on the fact that the copyingmachine terminates in standard position, which is required for theadding machine to correctly compute its result. By designing Turingmachines which start and end in standard configuration, we can ensurethat they may be composed in this manner. In the example, the copyingmachine has a unique terminating state, but this is not necessary. Wemight build a Turing machine which indicates the result of itscomputation by terminating on one of many states, and we can thecombine that machine with more that one machine, with the identity ofthe machine which follow dependent on the switching machine. This wouldenable us to create a machine which adds one to the input if that inputis even, and doubles it if odd, for example (should we want to for somereason).
Turing machines are very powerful. For a very large number ofcomputational problems, it is possible to build a Turing machine thatwill be able to perform that computation. We have seen that it ispossible to design Turing machines for arithmetic on the naturalnumbers, for example.
Computable Numbers
Turing's original paper concernedcomputable numbers. Anumber is Turing-computable if there exists a Turing machine whichstarting from a blank tape computes an arbitrarily preciseapproximation to that number. All of the algebraic numbers (roots ofpolynomials with algebraic coefficients) and many transcendentalmathematical constants, such ase and π areTuring-computable.
Computable Functions
As we have seen, Turing machines can do more than write downnumbers. Among other things they can compute numeric functions, such asthe machine for addition (presented inFigure 2) multiplication, proper subtraction, exponentiation, factorialand so on.
Thecharacteristic function of a predicate is a functionwhich has the value TRUE or FALSE when given appropriatearguments. An example would be the predicate ‘IsPrime’,whose characteristic function is TRUE when given a prime number, 2,3, 5 etc and FALSE otherwise, for example when the argument is 4, 9,or 12. By adopting a convention for representing TRUE and FALSE,perhaps that TRUE is represented as a sequence of two‘1’s and FALSE as one ‘1’, we can designTuring-machines to compute the characteristic functions ofcomputable predicates. For example, we can design a Turing machinewhich when started on a tape representing a number terminates withTRUE on the tape if and only if the argument is a prime number. Theresults of such functions can be combined using the using theboolean functions: AND, NOT, OR, IF-THEN-ELSE, each of which isTuring-computable.
In fact the Turing-computable functions are just the recursivefunctions, described below.
Universal Turing Machines
The most striking positive result concerning the capabilities ofTuring machines is the existence ofUniversal Turing Machines(UTM). When started on a tape containing the encoding of another Turingmachine, call itT, followed by the input toT, a UTMproduces the same result asT would when started on thatinput. Essentially a UTM can simulate the behavior of any Turingmachine (including itself).
One way to think of a UTM is as a programmable computer. When a UTMis given a program (a description of another machine), it makes itselfbehave as if it were that machine while processing the input.
Note again, our identification of input-output equivalence with“behaving identically”. A machineT working oninputt is likely to execute far fewer transitions that a UTMsimulatingT working ont, but for our purposes thisfact is irrelevant.
In order to design such a machine, it is first necessary to define away of representing a Turing machine on the tape for the UTM toprocess. To do this we will recall that Turing machines are formallyrepresented as a collection of 4-tuples. We will first design anencoding for individual tuples, and then for sequences of tuples.
Encoding Turing Machines
Each 4-tuple in the machine specification will be encoded as asequence of four blocks of ‘1’s, separated by a single‘0’
Using this convention the tuple ⟨0, ‘1’, 0,»⟩ would be represented as in Figure 5.
Figure 5: The Encoding of the Tuple ⟨0, ‘1’, 0,»⟩
To encode a complete machine, we need to simply write down thetuples on the tape, in any order, but separated from one another by twoblank cells so that we can tell where each tupe ends. The add-one machine ofFigure 1, would be represented by the somewhat intimidating string shown in Figure6.
… 010110101111 00 101011011 00 110110110111 00 11010111011110 …
Figure 6: The Encoding of the Machine in Figure 1
This construction shows that it is possible to encode the tupes ofa Turing machine on a Turing machine's tape (in fact we have done thisusing only the alphabet {0,1}, while we know from a previous resultthat we could have used an expanded alphabet which could have resultedin a more perspicuous representation). We want our UTM to be startedon a tape which contains the description of a Turing machine in thisencoding, followed by the arguments to this described Turing machine.We will adopt the convention that the description of the Turingmachine will be separated from the arguments by a block of three‘0’s, so the UTM can tell where the tuples end and thearguments begin. The add-one machine requires a single argumen, so wecould start the UTM on a tape as above followed by three‘0’s and, say, five ‘1’s. The UTM mustterminate on a tape which contains a single block of six‘1’s, having computed exactly what the add-one machinewould have done if started on a block of five ‘1’s.
In the previous section we described a way of encoding Turingmachines for input to a Universal Turing Machine. The encoding of aTuring machine is a sequence of ‘0’s and ‘1’and any such sequence can be interpreted as a natural number. We canthink of the encoding of a Turing machine as being a natural numberwhich is the serial number of that machine. Because of the way theencoding works, each Turing machine will have a distinct serialnumber. Since all of the serial numbers are natural numbers, thenumber of distinct Turing machines iscountably infinite.
On the other hand, the number of functions on the natural numbersis uncountable. There are (uncountably) more functions on the naturalnumbers than there are Turing machines, which shows that there areuncomputable functions, functions whose results cannot be computed byany Turing machine, because there are simply not enough Turingmachines to compute the functions.
This proof by counting is somewhat unsatisfactory, since it tells us that there are uncomputable functions, but provides us with no examples. Here we give two examples of uncomputable functions.
Imagine a Turing machine that is started on a completely blanktape, and eventually halts. If the machine leavesn ones onthe tape when it halts, we will say that theproductivity ofthis machine isn. We will say that the productivity of anymachine that does not halt is 0. Productivity is a function fromTuring machine descriptions (natural numbers) to natural numbers. Wewill writep(T)=n to indicate that the productivity ofmachineT isn.
Among the Turing machines that have a particular number of states,there is a maximum productivity that a Turing machine with that numberof states can have. This too is a function from natural numbers (thenumber of states) to natural numbers (the maximum productivity of amachine with that number of states). We will write this functionasBB(k)=n to indicate the maximum productivity ofak-state Turing machine isn. There may be multipledifferentk state machines with the maximumproductivityn. We call any of these machines a Busy Beaverfork.
There is no Turing machine which will compute thefunctionBB(k), i.e., which when started in standardconfiguration on a tape withk ‘1’s will halt instandard configuration on a tape withBB(k)‘1’s. This example is due to Tibor Radó(Radó 1962).
The proof that there is no such function proceeds by assuming thatthere is such a machine, i.e. that there is a machine which starts instandard configuration withk ‘1’s on the tape,and halts in standard configuration withBB(k)‘1’s on the tape. We will call this machineBand assume that it hask states.
There is ann-state machine which writesn‘1’s on an initially blank tape (exercise for the reader).We can construct a new machine which connects the halting state ofthis machine to the start state ofB and then connecting thehalting state ofB to the start state of another copyofB. So the first machine writesn ‘1’and then the first copy ofB computesBB(n), butthen the second copy ofB takes over andcomputesBB(BB(n)). The total number of states in ourmachine isn+2k. Our machine may be a Busy Beaverforn+2k, but it is certainly no more productive than such amachine. So (if the Busy Beaver machine exists)
BB(n+2k) ≥ BB(BB(n)),for anyn.
It is easy to show that the productivity of Turing machines increasesas states are added, i.e.,
ifi <j, then BB(i)< BB(j)
(another exercise). Consequently (if the Busy Beaver machine exists)
n+2k ≥ BB(n),for anyn.
Since this is true for anyn, it is true forn+11,yielding:
n+11+2k ≥ BB(n+11),for anyn.
But it is easy to show that BB(n+11) ≥ 2n(another exercise, but show that there is an eleven state machine fordoubling the number of ‘1’ on the tape, and compose such amachine with then-state machine for writingn‘1’s). Combining this fact with the previous inequality wehave:
n+11+2k ≥ BB(n+11) ≥ 2n, for anyn.
from which by subtractingn from both sides we have11+2k ≥n, for anyn, if the Busy Beaverexists, which is a contradiction.
Even though the productivity function is uncomputable, there isconsiderable interest in the search for Busy Beaver Turing machines(most productive machines with a given number of states). Somecandidates can be found by following links in theOther Internet resources section of this article.
It would be very useful to be able to examine the description of aTuring machine and determine whether it halts on a given input. Thisproblem is called theHalting problem and is, regrettably,uncomputable. That is, no Turing machine exists which computes thefunctionh(t,n) which is defined to be TRUEif machinet halts on inputn and FALSEotherwise.
To see the uncomputability of the halting function, imagine thatsuch a machineH exists, and consider a new machine built bycomposing the copying machine ofFigure 4 withH by joining the halt state of the copier to the startstate ofH. Such a machine, when started on a tape withn ‘1’s determines whether the machine whose code isn halts when given inputn, i.e., it computesM(n) =h(n,n).
Now lets add another little machine to the halt state ofH.This machine goes into an infinite sequence of transitions if the tapecontains TRUE when it starts, and halts if the tape contains FALSE (itsan exercise for the reader to construct this machine, assume that TRUEis represented by ‘11’, and FALSE by ‘1’).
This composed machine, call itM, halts if the machine withthe input coden does not halt on an initial tape containingn (because if machinen does not halt onn,the halting machine will leave TRUE on the tape, andM willthen go into its infinite sequence), and vice versa.
To see that this is impossible, consider the code forMitself. What happens whenM is started on a tape containingMs code? Assume thatM halts onM, then bythe definition of the machineM it does not halt. But equally,if it does not halt onM the definition ofM saysthat it should halt.
This is a contradiction, and the Halting machine cannot exist. Thefact that the halting problem is not Turing-computable was firstproved by Turing in (Turing 1937). Of course this result applies toreal programs too. There is no computer program which can examine thecode for a program and determine whether that program halts.
Recursive function theory is the study of the functions that can bedefined using recursive techniques (see the entry onrecursive functions). Briefly,the primitive recursive functions are those that can be formed from thebasic functions:
| the zero function: | z(x) | = | 0, | for allx |
| the successor function: | s(x) | = | x+1, | for allx |
| theith projection overjarguments: | pi,j(x0,…xj) | = | xi, | for allxi, i, j |
by using the operations of composition and primitive recursion:
| Composition: | ||||||||||||
| ||||||||||||
| ||||||||||||
| The recursive functions are formed by the addition of the minimizationoperator, which takes a functionf and returnshdefined as follows: | ||||||||||||
|
It is known that the Turing computable functions are exactly therecursive functions.
Abacus machines abstract from the more familiar architecture of themodern digital computer (the von Neumann architecture). In its simplestform a computer with such an architecture has a number of addressableregisters each of which can hold a single datum, and a processor whichcan read and write to these registers.
The machine can perform two basic operations, namely: add one to thecontent of a named register (which we will symbolize asn+,wheren is the name of the register) and (attempt to) subtractone from a named register, with two possible outcomes: a success branchif the register was initially non-zero, and a failure branch if theregister was initially zero (we will symbolize the operation asn-).
These are calledabacus computers by Lambek (Lambek 1961),and are known to be equivalent to Turing machines.
The modern digital computer is subject to finiteness constraintsthat we have abstracted away in the definition of abacus machines, justas we did in the case of Turing machines. Physical computers arelimited in the number of memory locations that they have, and in thestorage capacity of each of those locations, while abacus machines arenot subject to those constraints. Thus some abacus-computable functionswill not be computable by any physical machine. (We won't considerwhether Turing machines and modern digital computers remain equivalentwhen both are given external inputs, since that would require us tochange the definition of a Turing machine.)
One way to modify the definition of Turing machines is by removingtheir ability to write to the tape. The resulting machines are calledfinite state machines. They are provably less powerful thanTuring machines, since they cannot use the tape to remember the stateof the computation. For example, finite state machines cannot determinewhether an input string consists of some As followed by the same numberof Bs. The reason is that the machine cannot remember how many As ithas seen so far, except by being in a state that represents this fact,and determining whether the number of As and Bs match in all caseswould require the machine to have infinitely many states (one toremember that it has seen one A, one to remember that it has seen 2,and so on).
How to cite this entry. Preview the PDF version of this entry at theFriends of the SEP Society. Look up this entry topic at theIndiana Philosophy Ontology Project (InPhO). Enhanced bibliography for this entryatPhilPapers, with links to its database.
Turing machines are more powerful than any device that canactually be built, but they can be simulated both in software andhardware.
There are many Turing machine simulators available. Here are threesoftware simulators that use different technologies to implementsimulators using your browser.
Here are is an application that you can run on the desktop (noendorsement of these programs is implied).
Church, Alonzo |Church-Turing Thesis |computability and complexity |function: recursive |Turing, Alan
