Friday, January 03, 2003

Foundations of Complexity
Lesson 12: Turing Machine Redux

Previous Lesson | Next Lesson

Back in Lesson 1 we gave an informal description of a Turing machine as any computer program. That was fine for computability, but for complexity we need to give a more specific, but still informal, definition.

A one-tape Turing machine consists of an infinitely long "tape" consisting of tape cells that each can carry one of a finite set Γ of tape symbols. Typically we have Γ={0,1,B}. The Turing machine has a finite memory, where Q represents the set of all possible states of that memory. The Turing machine also has a tape head that points a specific location on the tape.

Initially the input is put somewhere on the tape with the rest of the tape having the special "B" blank symbol. The tape pointer points to the beginning of the input. The Turing machine starts out in some initial state q0.

In each iteration the Turing machine looks at the tape character under the head and the current state. It writes a new character under the head and then moves the head one step left or right and then enters a new state depending on its instructions.

If the Turing machine enters the accept state qa then it halts and accepts. If the Turing machine enters the reject state qr then it halts and rejects. Otherwise the process repeats.

This simple model captures all of the computational power of much more general Turing machine. It also does this with at most a polynomial slow-down, i.e., if a problem of size n was solved in t(n) steps on a more complex machine it can be solved in time (t(n))k on a one-tape Turing machine for some fixed k.

A deterministic Turing machine's choice of next state, character to write and direction to move the tape is a function of the previous state and current character under the tape. A nondeterministic machine may allow several options and if one series of options leads to acceptance we say the nondeterministic machine accepts.

A configuration of a Turing machine is a snapshot in time of the machine and consists of the tape contents, the current state and the location of the head pointer.

A tableau is a list of configurations

A proper tableau for a machine M and input x is a tableau where
  1. conf0 is the initial configuration for M with input x.
  2. confm is a configuration in the accept state.
  3. For all i, 0 ≤ i < m, confi+1 follows from confi in one step.
A machine M accepts input x if and only if there is a proper tableau for M and x.


  1. If a non-deterministic machine accepts on some paths and rejects on others, does it accept or reject?

    1. A non-deterministic machine accepts if any path accepts. It doesn't matter what happens on the other paths.