Symmetric Turing machine

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A symmetric Turing machine is a special kind of Turing machine whose configuration graph is undirected: if one configuration can move to another, the reverse move is also possible. In this model, transitions look like (p, ab, D, cd, q), where p and q are states, ab and cd are pairs of symbols, and D is a direction (left or right). If D is left, the machine, in state p while seeing a on the left and b on the tape, can move left, change to state q, and replace ab with cd. The opposite transition (q, cd, -D, ab, p) is always allowed. The right-move version is analogous. Using two symbols at a time (peek-and-replace) isn’t essential, but makes the idea clearer. Symmetric TMs were defined in 1982 by Lewis and Papadimitriou, who wanted a class to study the undirected graph problem USTCON (is there a path between two vertices s and t).

Key ideas:
- STIME(T) is the set of languages a symmetric TM can accept in time O(T(n)).
- It holds that STIME(T) = NTIME(T): any nondeterministic TM running in time T can be simulated by a symmetric TM by letting nondeterminism occur at the start and then running deterministically.
- SSPACE(S(n)) is the class of languages accepted by symmetric TMs using space O(S(n)).
- SL equals SSPACE(log n); equivalently, SL are problems that can be reduced in logspace to USTCON (the undirected graph connectivity problem).

Historical milestones:
- Lewis and Papadimitriou showed how to convert a nondeterministic machine for USTCON into an equivalent symmetric TM, linking USTCON to the symmetric model.
- In 2004, Omer Reingold proved SL = L by giving a deterministic log-space algorithm for USTCON, using the zig-zag product to build expander graphs. This breakthrough earned him the Grace Murray Hopper Award (2005) and, together with Avi Wigderson and Salil Vadhan, the Gödel Prize (2009).