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 q_{0}.

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 q_{a} then it
halts and accepts. If the Turing machine enters the reject state
q_{r} 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

_{0}#conf

_{1}#...#conf

_{m}.

*proper tableau*for a machine M and input x is a tableau where

- conf
_{0}is the initial configuration for M with input x. - conf
_{m}is a configuration in the accept state. - For all i, 0 ≤ i < m, conf
_{i+1}follows from conf_{i}in one step.

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

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

Delete