Symmetric Turing machine

Definition of symmetric Turing machines

A symmetric Turing machine is a variant that uses transitions written as pab → qcdD. Here, p and q are states, ab and cd are pairs of tape symbols, and D indicates a direction. When D is left, a machine in state p with its head reading symbol b, where a is the symbol immediately to the left, can move left, switch to state q, and replace a and b with c and d. The reverse transition pcd → qabD is always available. The case for D right works similarly.

The ability to read and write two symbols at once is not essential but makes the definition easier. This model was introduced in 1982 by Harry R. Lewis and Christos Papadimitriou. They were looking for a complexity class to contain USTCON, the problem of checking whether two vertices in an undirected graph are connected. Previously, USTCON could only be placed in NL, even though it did not seem to require nondeterminism; the directed version STCON was already known to be NL-complete.

Symmetric Turing machines have limited nondeterministic power and are at least as strong as deterministic Turing machines. The class STIME(T(n)) contains all languages accepted by a symmetric Turing machine within time T(n). It can be shown that STIME(T(n)) is a subset of NTIME(T(n)) by restricting nondeterminism to an initial phase where a string is written nondeterministically, after which the computation becomes deterministic.