A symmetric Turing machine is a

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

which has a

configuration graph Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes. Definition A theoretical computational model, like Turing machine or finite automata, expl ...

that is undirected (that is, configuration i yields configuration j if and only if j yields i).

Definition of symmetric Turing machines

Formally, we define a variant of Turing machines with a set of transitions of the form , where ''p,q'' are states, ''ab,cd'' are pairs of symbols and ''D'' is a direction. If ''D'' is ''left'', then the head of a machine in state ''p'' above a tape symbol ''b'' preceded by a symbol ''a'' can be transitioned by moving the head left, changing the state to ''q'' and replacing the symbols ''a,b'' by ''c,d''. The opposite transition can always be applied. If ''D'' is right the transition is analogous. The ability to peek at two symbols and change both at a time is non-essential, but makes the definition easier. Such machines were first defined in 1982 by Harry R. Lewis and

Christos Papadimitriou Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...

, who were looking for a class in which to place

USTCON In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (''undirected s-t connectivity''), which is the problem of determining whether there exists a path between two ve ...

, the problem asking whether there is a path between two given vertices s,t in an undirected graph. Until this time, it could be placed only in NL, despite seeming not to require

nondeterminism Nondeterminism or nondeterministic may refer to: Computer science *Nondeterministic programming *Nondeterministic algorithm *Nondeterministic model of computation **Nondeterministic finite automaton **Nondeterministic Turing machine *Indeterminacy ...

(the asymmetric variant STCON was known to be complete for NL). Symmetric Turing machines are a kind of Turing machine with limited nondeterministic power, and were shown to be at least as powerful as deterministic Turing machines, giving an interesting case in between. is the class of the languages accepted by a symmetric Turing machine running in time . It can easily proved that by limiting the nondeterminism of any machine in to an initial stage where a string of symbols is nondeterministically written, followed by deterministic computations.

(S(''n'')) is the class of the languages accepted by a symmetric Turing machine running in space and =(log(''n'')). SL can equivalently be defined as the class of problems

logspace In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition&n ...

reducible to USTCON. Lewis and Papadimitriou by their definition showed this by constructing a nondeterministic machine for USTCON with properties that they showed are sufficient to make a construction of an equivalent symmetric Turing machine possible. Then, they observed that any language in SL is logspace reducible to USTCON as from the properties of the symmetric computation we can view the special configuration as the undirected edges of the graph. In 2004,

Omer Reingold Omer Reingold ( he, עומר ריינגולד) is an Israeli computer scientist. He is the Rajeev Motwani professor of Computer Science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the Th ...

proved that SL=L by showing a deterministic algorithm for USTCON running in logarithmic space, for which he received the 2005

Grace Murray Hopper Award The Grace Murray Hopper Award (named for computer pioneer RADM Grace Hopper) has been awarded by the Association for Computing Machinery (ACM) since 1971. The award goes to a computer professional who makes a single, significant technical or serv ...

and (together with

Avi Wigderson Avi Wigderson ( he, אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jerse ...

and

Salil Vadhan Salil Vadhan is an American computer scientist. He is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. After completing his undergraduate degree in Mathematics and Computer Science at Harvard in 1995, he ...

) the 2009

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

. The proof uses the

zig-zag product In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, is a binary operation which takes a large graph (G) and a small graph (H) and produces a graph that approximately inherits the size of the large one but the degree o ...

to efficiently construct

expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applicati ...

Notes

{{Reflist

References

* Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha
Lecture Notes
* Sharon Bruckner Lecture Notes * Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson Alan Turing Computational complexity theory Turing machine