Turing Machines (Stanford Encyclopedia of Philosophy) Cite this entry Search the SEP • Advanced Search • Tools • RSS FeedTable of Contents• What's New• Archives• Projected ContentsEditorial Information• About the SEP• Editorial Board• How to Cite the SEP• Special CharactersSupport the SEPContact the SEP ©Metaphysics Research Lab,CSLI,Stanford University  Open access to the SEP is made possible by a world-wide funding initiative. Please Read How You Can Help Keep the Encyclopedia FreeTuring MachinesFirst published Thu Sep 14, 1995; substantive revision Fri Nov 5, 2004Turing machines, first described by Alan Turing in (Turing 1937),are simple abstract computational devices intended to help investigatethe extent and limitations of what can be computed.Turing, writing before the invention of the modern digital computer,was interested in the question of what it means to be computable.Intuitively a task is computable if one can specify a sequence ofinstructions which when followed will result in the completion of thetask. Such a set of instructions is called an effectiveprocedure, or algorithm, for the task. This intuitionmust be made precise by defining the capabilities of the device that isto carry out the instructions. Devices with different capabilities maybe able to complete different instruction sets, and therefore mayresult in different classes of computable tasks (see the entryon computability 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 call Turing-computability.The proposition that Turing's notion captures exactly the intuitiveidea of effective procedure is called the Church-Turing thesis. This proposition, being a claim about the relationship between aformal concept and intuition, is not provable, though it would berefuted by an intuitively acceptable algorithm for a task that is notTuring-computable. That no such counterexample has been found,together with the fact that Turing-computability is equivalent toindependently defined notions of computability based on alternativefoundations, such as recursive functions andabacus machines, indicates that there is at least something naturalabout 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 about how 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.1. A Definition of Turing Machine 1.1 The Definition Formalized2. Describing Turing Machines 2.1 Examples2.2 Instantaneous Descriptions of a Computation3. Varieties of Turing Machines4. What Can Be Computed5. What Cannot Be Computed 5.1 The Busy Beaver5.2 The Halting Problem6. Alternative Formulations of Computability 6.1 Recursive Functions6.2 Abacus Machines7. Restricted Turing MachinesBibliographyOther Internet ResourcesRelated Entries1. A Definition of Turing MachinesA Turing machine is a kind of state 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.A Turing machine has an infinite one-dimensional tape 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 a read-write head, which at any timescanning 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:< State0, Symbol,Statenext, Action >which can be read as saying “if the machine is in stateState0 and the current cell containsSymbol then move into state Statenexttaking Action”. The actions available to a Turingmachine are 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 not exactly onetransition rule specified, i.e., 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 definition. The first is that the machine's tape is infinitein length, corresponding to an assumption that the memory of themachine is infinite. The second is similar in nature, but not explicitin the definition of the machine, namely that a function will beTuring-computable if there exists a set of instructions that willresult in the machine computing the function regardless of the amountof time it takes. One can think of this as assuming the availability ofinfinite time to complete the computation.These two assumptions are intended to ensure that the definition ofcomputation that results is not too narrow. This is, it ensures that nocomputable function will fail to be Turing-computable solely becausethere is insufficient time or memory to complete the computation. If afunction is not Turing-computable it is because Turing machines lackthe computational machinery to carry it out, not because of a lack ofspatio-temporal resources.1.1. The Definition FormalizedTalk 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: A finite set of states Q with a distinguished startstate,A finite set of symbols ΣA computation state of the machine can be described Qstate a member of Q.A function σstate from the natural numbers intoΣ.A natural number hstate.The transition function for the machine δ is a functionfrom computation states to computation states, such that ifδ(S) = T σT agrees withσS everywhere except onhS (and perhaps there too.)If σS(hS) ≠σT(hS) thenhT = hS otherwise,|hT − hS| ≤ 1 A formal definition such as this facilitates the analysis of theconcept of Turing machine, at the cost of obscuring the underlyingintutions about such machines. To see how the formal definitionrelates to the original one, think of the function σ asrepresenting the tape by assigning an index to each cell of the tape,and then encoding the symbol in that cell as the value of the functionσ given the index of the cell.The read-write head is represented by the number h which isthe index of the cell scanned by the head.The transition function determines the new content of the tape byreturning a new function σ but this new function isconstrained to differ from the original in at most the cell beingscanned. If that cell is modified, then the head must not be moved inthe transition, and if it is not modified, then the head is constrained tomove at most one cell in either direction.This definition is very similar to that given in the entry on computability and complexity, with the significant difference that thetransition function 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.2. Describing Turing MachinesEvery 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, » >When we are interested in examining the behaviour of a Turingmachine, it is common and perhaps more perspicuous to represent themachine using a state diagram. Here is the machine represented in thisformat.  Figure 1: A State DiagramIn 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.2.1 ExamplesIn 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 number nas a block of n+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 requires n arguments, then the Turing machinewill start with its head scanning the leftmost ‘1’ of asequence of n 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. 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 in Figure 1 describes a machine which computes the successor (add-one)function. That is when started in standard configuration on a taperepresenting the number n it will halt in standardconfiguration representing the number n+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 state s2.You can see a movie of the execution of this machine here.For another example, consider the machine in Figure 2 which computesthe addition function. That is, when started on a standard taperepresenting the numbers n and m, the machine haltson a tape representing n+m.  Figure 2: A Machine for Computingn+m Notice that this machine is like the add one machine in that statess0 through s 2 cause the machine to write a‘1’ to the right of the first block of ‘1’s,and returns the head to the leftmost ‘1’. In standardconfiguration for addition, this joins the two blocks of‘1’s into a single block, containing(n+1)+1+(m+1) copies of the symbol‘1’, so that on entering state s2 the taperepresents the number n+m+2. In order to correctthis, we need to remove two copies of the symbol ‘1’,which is achieved by states s 2 and s3, each ofwhich replaces a ‘1’ by ‘0’ and then moves tothe right.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.2.2 Instantaneous Descriptions of a ComputationThe complete state of a Turing machine at any point during acomputation may be described by the name of the state that the machineis in, the symbols on the tape, and the cell that is currently beingscanned. A description of these three data is called aninstantaneous description of the computation. We willrepresent such a description using a figure like that in Figure 3, inwhich the arrow represents the currently scanned cell and the name ofthe current state is written below the arrow.  Figure 3: The Instantaneous Description of a Turing MachineComputation3. Varieties of Turing MachinesWe 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. Formulation F1 and formulationF2 are equivalent if for every machinedescribed in formulation F1 there is machine adescribed in F2 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,at the left say, and stretched infinitely far to the right. Relaxingthis stipulation to allow the tape to stretch infinitely far to rightand left results in a new formulation of Turing machines equivalent tothe original. That is for any Turing machine using a two way tape thereis a Turing machine with a one-way infinite tape with the sameinput-output behavior, and vice versa. 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 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. Arbitrary finite alphabet In our original formulation we allowed the use of only two symbolson the tape. In fact we do not increase the power of Turing machines byallowing the use of any finite alphabet of symbols. 5-tuple formulationA 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 >where Symbolnew is the symbol written,and Move 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 as accepting 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 originalones 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 state s1. In state s1 weskip the remainder of the block of ‘1’s until we find a‘0’ (the block separator) and in s2 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 state s3. Statess3 and s4 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 state s5, 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 of Figure 2 to construct a doubling machine, i.e. a machine which, when startedon a tape representing the number n halts on a taperepresenting 2n. We could do this by first using the copyingmachine to produce a tape with two copies of n on the tape,and then using the addition machine to compute n+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).4. What Can Be ComputedTuring 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 concerned computable 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 as e 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 in Figure 2) multiplication, proper subtraction, exponentiation, factorialand so on.By adopting a convention for representing TRUE and FALSE, perhaps thatTRUE is represented as a sequence of two ‘1’s and FALSE asone ‘1’, we can compute the characteristic functions ofcomputable predicates, and we may combine the results of suchfunctions using the boolean functions: AND, NOT, OR, IF-THEN-ELSE.In fact the Turing-computable functions are just the recursivefunctions, described below. Universal Turing MachinesThe most striking positive result concerning the capabilities ofTuring machines is the existence of Universal Turing Machines(UTM). When started on a tape containing the encoding of another Turingmachine, call it T, followed by the input to T, a UTMproduces the same result as T 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 machine T working oninput t is likely to execute far fewer transitions that a UTMsimulating T working on t, 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 MachinesEach 4-tuple in the machine specification will be encoded as asequence of four blocks of ‘1’s, separated by a single‘0’The first block of ones will encode the current state number, usingthe unary number convention above (n+1 ones represents thenumber n).The second block of ones will encode the current symbol, using one‘1’ to represent the symbol zero, and two to represent thesymbol ‘1’ (again because we can't use zero ones torepresent ‘0’.)The third element of the tuple will represent the new state numberin unary number notation.The fourth element represents the action, and there are fourpossibilities: symbols will be encoded as above, with a block of three‘1’s representing a move to the left («) and a blockof four ‘1’s representing a move to the right(»).Using this convention the tuple <0, ‘1’, 0, »> would berepresented as in Figure 4.  Figure 4: 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. The add-one machine of Figure 1, would be represented by the somewhat intimidating string shown in Figure5. … 010110101111 00 101011011 00 110110110111 0011010111011110 …Figure 5: The Encoding of the Machine in Figure1If we interpret encodings such as that in Figure 5 as a binarynumber (ignoring trailing zeros), we see that each Turing machine has aserial number.5. What Cannot Be ComputedA crucial observation about Turing machine is that there are onlycountably many machines (a set is countable if it is finite, or may beplaced in one-to-one correspondence with the integers.) It followsimmediately that there are uncountably many real numbers that are notcomputable, since the reals are not countable. There are simply notenough Turing machines to compute all of those numbers.Like the real numbers, the number of functions on the naturalnumbers is not countable. It follows therefore that there areuncountably many such functions that are not computable by any Turingmachine.Here we give two examples of uncomputable functions.5.1 The Busy BeaverDefine the productivity of a Turing machine as the number ofones on the tape when it halts in standard configuration, if it does,and 0 if it does not. The machine is assumed to start in its lowestnumber state and with an initially blank tape. Now definep(n) to be the productivity of the most productiven-state machine. There is no Turing machine which willcompute the function p, i.e., which when started in standardconfiguration on a tape with n ‘1’s will halt instandard configuration on a tape with p(n)‘1’s. This example is due to Tibor Radó(Radó 1962).We can prove the uncomputability of the busy beaver function byderiving a contradiction from the assumption that such a machineexists. The crucial step in the proof, is to note that if the BusyBeaver machine were to exist, the productivity of the most productiven+2k state machine is at leastp(p(n)), where k is the number ofstates of the (alleged) Busy Beaver machine. This is demonstrated bybuilding a machine which initially writes n ‘1’son the tape (which can be done in n states — exercisefor the reader), and then connecting the halt state of that machine tothe start state of the Busy Beaver machine (resulting in a computationof p(n)), and then connecting the halt state of thatmachine with another copy of the Busy Beaver machine, resulting acomputation of p(p(n)). Thus (if the BusyBeaver machine exists)p(n+2k) ≥ p(p(n))for any n.It is easy to show that the productivity of Turing machines increasesas states are added, i.e. if i < j, then p(i)< p(j)(another exercise). Consequently (if the Busy Beaver machine exists) n+2k ≥ p(n)for any n.Since this is true for any n, it is true for n+11,yielding: n+11+2k ≥ p(n+11)for any n.But it is easy to show that p(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 the n-state machine for writing n‘1’s). Combining this fact with the previous inequality wehave:n+11+2k ≥ p(n+11) ≥ 2n for any n.from which by subtracting n from both sides we have11+2k ≥ n for any n 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 the Other Internet resources section of this article.5.2 The Halting ProblemIt 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 the Halting problem and is, regrettably,uncomputable. That is, no Turing machine exists which computes thefunction h(t,n) which is defined to be TRUEif machine t halts on input n and FALSEotherwise.To see the uncomputability of the halting function, imagine thatsuch a machine H exists, and consider a new machine built bycomposing the copying machine of Figure 4 with H by joining the halt state of the copier to the startstate of H. Such a machine, when started on a tape withn ‘1’s determines whether the machine whose code isn halts when given input n, i.e. it computesM(n) = h(n,n).Now lets add another little machine to the halt state of H.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 it M, halts if the machine withthe input code n does not halt on an initial tape containingn (because if machine n does not halt on n,the halting machine will leave TRUE on the tape, and M willthen go into its infinite sequence.) and vice versa.To see that this is impossible, consider the code for Mitself. What happens when M is started on a tape containingMs code? Assume that M halts on M, then bythe definition of the machine M it does not halt. But equally,if it does not halt on M the definition of M saysthat it should halt.This is a contradiction, and the Halting machine cannot exist. Thefact that the halting problem is not Turing-computable was first provedby Turing in (Turing 1937).6. Alternative Formulations of Computability6.1 Recursive FunctionsRecursive function theory is the study of the functions that can bedefined using recursive techniques (see the entry on recursive functions). Briefly,the primitive recursive functions are those that can be formed from thebasic functions:the zero function:z(x)=0,for all xthe successor function:s(x)=x+1,for all xthe ith projection over jarguments:pi,j(x0,…xj)=xi,for all xi,i,jby using the operations of composition and primitive recursion:Composition: f(x1,…,xn)=g(h1(x1,…,xn),…,hm(x1,…,xn)),for all g,h1,…,hmPrimitive Recursion:f(x,0)=g(x),for any gf(x,s(y))=h(x,y,f(x,y)),for any hThe recursive functions are formed by the addition of the minimizationoperator, which takes a function f and returns hdefined as follows: Minimization:h(x1,…,xn)=y, if f(x1,…,xn,y)=0 and∀t<y(f(x1, …,xn,t)is defined and positive) =undefined otherwise.It is known that the Turing computable functions are exactly therecursive functions.6.2 Abacus MachinesAbacus machines abstract 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 as n+,where n 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 called abacus 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.)7. Restricted Turing MachinesOne 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.) BibliographyBarwise, J. and Etchemendy, J., 1993, Turing'sWorld, Stanford: CSLI Publications.Boolos, G.S. and Jeffrey, R.C., 1974, Computability and Logic,Cambridge: Cambridge University Press.Davis, M., 1958, Computability and Unsolvability, McGraw-Hill; reprinted Dover 1982.Herken, R., (ed.), 1988, The Universal Turing Machine: A Half-CenturySurvey, New York: Oxford University Press.Hodges, A., 1983, Alan Turing, The Enigma, New York: Simon andSchuster.Kleene, S.C., 1936, "General recursive Functions of Natural Numbers".Mathematische Annalen, 112.Lambek, J., 1961, "How to program an infinite abacus", CanadianMathematical Bulletin, 4: 279–293.Lewis, H.R. and Papadimitriou, C.H., 1981, Elements of the Theory ofComputation, Prentice-Hall.Lin, S. and Radó, T., 1965, "Computer Studies of Turing MachineProblems," Journal of the Association for Computing Machinery, 12,196–212.Post, E., 1947, "Recursive Unsolvability of a Problem of Thue," TheJournal of Symbolic Logic, 12.Radó, T., 1962, "On Non-computable functions", Bell SystemTechnical Journal, May.Turing, A.M., 1936-7, "On Computable Numbers, With an Applicationto the Entscheidungsproblem", Proceedings of the LondonMathematical Society, (2) 42, pp 230-265; correctionibid. 43, pp 544-546 (1937). [Available Online].Turing, A.M., 1937, "Computability and λ-Definability",The Journal of Symbolic Logic, 2. Other Internet Resources"Turing Machines", Stanford Encyclopedia of Philosophy(Summer 2003 Edition), Edward N. Zalta (ed.), URL = <http://plato.stanford.edu/archives/sum2003/entries/turing-machine/>. [This was the original version of the present entry, written by theEditors of the Stanford Encyclopedia of Philosophy.] The Alan Turing Home PageBusy BeaverTuring's World Busy Beaver pageMichael Somos' page of Busy Beaver references.The Halting ProblemHalting problem solvable (funny)Online Turing Machine SimulatorsThere are many Turing machine simulators available. Here are three thatuse different technologies to implement simulators using your browser. Andrew Hodges' Turing Machine Simulator (for limitednumber of machines)Suzanne Britton's Turing Machine Simulator (A Java Applet)Here are is an application that you can run on the desktop (noendorsement of these programs is implied). Visual Turing: freeware simulator for Windows 95/98/NT/2000During the second world war, Alan Turing was involved in code breakingactivites at Station X in Bletchley Park in the UK. Related Entries Church, Alonzo | Church-Turing Thesis | computability and complexity | function: recursive | Turing, Alan Copyright © 2004 byDavid Barker-Plummer<dbp@csli.stanford.edu> |
|
