Turing Machines Overview

Math for CS · Axiom Academy

The mathematical model that defines what it means to "compute" PDAs failed to count three things at once. The fix: replace the stack with an infinite tape that the head can move freely on. A pushdown automaton can only see the top of its stack. If we let the machine move its read/write head left or right over an unbounded memory, suddenly we can revisit earlier symbols, mark them off, and coordinate arbitrarily many counts. This single upgrade — random-access memory in the form of a tape — is enough to capture everything that any modern computer can do. Alan Turing introduced this model in his 1936 paper "On Computable Numbers." He invented it not to build hardware, but to give a precise mathematical answer to the question: what does it mean for a procedure to be "mechanical"? A Turing machine is a 7-tuple. The new ingredient is a transition function that writes and moves the head. is the input alphabet (does not contain the blank symbol ) is the tape alphabet, with and are halting states (must be distinct) A single transition step means: in state q reading a , move to state p , write b over a , and shift the head one cell in direction . The tape is infinite to the right, with blanks ( ) filling all unused cells. The head starts on the leftmost input symbol. Computation continues until the machine enters or — or runs forever, in which case the machine is said to loop . Step 3: A TM that Accepts Equal a 's and b 's

This is the written version of the interactive lesson above. See the full Math for CS course.