Turing machine

A Tur­ing Ma­chine is a sim­ple math­e­mat­i­cal model of com­pu­ta­tion that is pow­er­ful enough to de­scribe any com­pu­ta­tion a com­puter can do.

Imag­ine a robot, in front of a lit­tle white­board, with in­finitely many white­boards to both sides, finitely many of which have a sym­bol writ­ten on them. The robot can erase the con­tents of a white­board and re­place it with some other sym­bol, and it can move over to the next white­board on the left or right, or shut down. This is all the robot can do. The robot’s ac­tions are de­ter­mined by only two things: the sym­bol on the white­board it just saw, and its in­ter­nal state. The out­put of this pro­cess is defined to be “what­ever is writ­ten on the string of white­boards when the robot has shut down”.

This is equiv­a­lent to a Tur­ing Ma­chine (with the robot re­placed by a ma­chine head and the in­finite line of white­boards re­placed by an in­finite tape sub­di­vided into cells). The halt­ing prob­lem (which is un­solv­able in gen­eral) asks whether the robot will even­tu­ally shut down at some point.

So, a Tur­ing Ma­chine can be speci­fied with the fol­low­ing in­for­ma­tion:

  • A finite set of sym­bols the robot can write (one of which is the null sym­bol, an empty board).

  • A finite set of states the robot can be in (at least one of which causes the robot to shut down).

  • A start­ing state for the robot.

  • Start­ing sym­bols on finitely many of the boards (white­board lo­ca­tion and sym­bol type data).

  • A tran­si­tion func­tion for the robot, which takes a sym­bol/​state pair as in­put, and has a \((\text{symbol},\text{state},\text{move left or right})\) triple as out­put. For ex­am­ple, ine such tran­si­tion might be rep­re­sented as if sym­bol is 7 and state is FQUF, then (erase and write 4, set state to ZEXA, move left).

Sur­pris­ingly enough, other pro­posed mod­els of com­pu­ta­tion have all been shown to be weaker than, or equiv­a­lent to, Tur­ing Machines! With in­finite mem­ory space, and suffi­ciently in­tri­cate sets of sym­bols and states, the robot and white­board (or ma­chine head and mem­ory tape) sys­tem can com­pute any­thing at all that is com­putable in prin­ci­ple! This fact is known as the Church-Tur­ing the­sis; it’s very widely be­lieved to be true, and cer­tainly no-one has ever found any hint of a coun­terex­am­ple, but it’s not “proved” in any mean­ingful sense.

Var­i­ants of Tur­ing machines

Multi-tape Tur­ing Machines would be equiv­a­lent to hav­ing sev­eral robots in in­finite white­board hal­lways, ex­cept that the robots are net­worked to­gether to all share the same state. An ex­am­ple state tran­si­tion is as fol­lows:

If sym­bol A is \* and sym­bol B is 6 and sym­bol C is ab­sent and state is VREJ, set state to IXXI, robot A writes ! and moves left, robot B writes 9 and moves left, robot C writes = and doesn’t move.

Th­ese Multi-tape Machines can speed up some com­pu­ta­tions polyno­mi­ally (so, for ex­am­ple, a prob­lem which would nor­mally take 1 mil­lion steps to solve may be solv­able in a thou­sand steps, be­cause of the square root speedup). Be­cause these ma­chines can only muster a polyno­mial speedup, and mov­ing to a one-tape Tur­ing Ma­chine only in­curs a polyno­mial slow­down, the com­pu­ta­tional com­plex­ity class P is un­changed across Tur­ing Machines with differ­ent num­bers of tapes.

Write-only Tur­ing Machines are Multi-tape Tur­ing Machines where one of the tapes/​hal­lways of white­boards has its in­put ig­nored when de­ter­min­ing the next state, writ­ten sym­bols and move­ments. We can think of this situ­a­tion as one where one par­tic­u­lar robot is blind.

Read-only Tur­ing Machines are Multi-tape Tur­ing Machines, and one of the tapes/​hal­lways of white­boards can­not be rewrit­ten. The robot in there can only move around and ob­serve, but it has not been given a pen or rub­ber so it can’t write on or erase the boards.

Or­a­cle Machines (which are more pow­er­ful than Tur­ing Machines, and don’t ex­ist in re­al­ity, though they are a very use­ful tool in com­pu­ta­tional com­plex­ity the­ory), are like a mult-tape ma­chine with ex­actly two tapes: one tape is des­ig­nated as the “or­a­cle tape”, and one tape as the “ma­chine tape”. This time, one of the robot states is “INVOKING MAGIC ORACLE”. When that hap­pens, the con­tents of the white­boards in the ma­chine hall (that is, the con­tents of the ma­chine tape) are in­ter­preted as the de­scrip­tion of a prob­lem, and then a cor­rect solu­tion to the prob­lem mag­i­cally ap­pears on the string of white­boards in the or­a­cle hall (that is, on the or­a­cle tape), com­pletely eras­ing what­ever was on the or­a­cle hall white­boards origi­nally; and fi­nally the or­a­cle robot is moved to the first white­board of the an­swer.

There­fore the func­tion­al­ity of the or­a­cle ma­chine de­pends very strongly on what the or­a­cle does! A given or­a­cle ma­chine might do one thing when the or­a­cle does “com­pute the fac­to­rial of the num­ber I was called with” than when it does “com­pute whether or not the num­ber I was given is the de­scrip­tion num­ber of a halt­ing Tur­ing ma­chine”.

Or­a­cle ma­chines are like or­di­nary Tur­ing ma­chines, ex­cept we also give them the abil­ity (in prin­ci­ple) to ob­tain in­stant cor­rect an­swers to any par­tic­u­lar prob­lem. The prob­lem we may in­stantly solve is fixed in ad­vance, be­fore we ever start run­ning the ma­chine. With the right or­a­cle, or­a­cle ma­chines can solve any prob­lem, where Tur­ing ma­chines can­not (re­call­ing that the halt­ing prob­lem can’t be solved by Tur­ing ma­chines). How­ever, the price is that or­a­cle ma­chines don’t ex­ist: they re­quire a magic or­a­cle, and we don’t have any of those in na­ture.

Children:

  • Rice's Theorem

    Rice’s The­o­rem tells us that if we want to de­ter­mine pretty much any­thing about the be­havi­our of an ar­bi­trary com­puter pro­gram, we can’t in gen­eral do bet­ter than just run­ning it.

  • Turing machine: External resources

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.