**Symmetric Turing Machine**

A Symmetric TM is a TM which has a configuration graph that is undirected. That is configuration i yields configuration j if and only if j yields i. The set of languages that have a symmetric TM deciding it in log space is called SL. It was first defined in 1982 by Lewis and Papadimitriou, who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in NL, despite seeming not to require nondeterminism. They defined the symmetric Turing machine, used it to define SL. Symmetric Turing machines are kind of Turing machines with limited nondeterministic power. Informally Symmetric computations are reversible in an approximate manner. A symmetric computation is divided into locally deterministic sub computation (segments) between special configuration, where nondeterminism takes place, such that the only special configuration reached from a backward computation is the special configuration started the segment. Thus the segments are locally deterministic in its forward direction and have limited nondeterminism in its backward direction. Also if there is a way from special configuration A1 to special configuration A2, there must be a way back from A2 to A1.

Example of Symmetric Configuration

Read more about Symmetric Turing Machine: Symmetric Log Space Complexity, Idea About Why USTCON Is SL-complete

### Other articles related to "turing, machines, symmetric turing machine, machine, symmetric, turing machines, turing machine":

... The

**Turing**test is a way of considering the question of whether

**machines**can think, proposed by Alan

**Turing**... The

**Turing**Test may also refer to The

**Turing**Test (Doctor Who), a Doctor Who novel featuring Alan

**Turing**as a character The

**Turing**Test, a chamber opera composed by Julian Wagstaff The Ideological ...

**Symmetric Turing Machine**- Idea About Why USTCON Is SL-complete

... They constructed a nondeterministic

**machine**for USTCON, and they made a lemma for converting this

**machine**into

**Symmetric Turing Machine**... Then the theorem follows as any language can be accepted using a

**symmetric Turing machine**is logspace reducible to USTCON as from the properties of the

**symmetric**...

... The Computer Game Bot

**Turing**Test is a variant of the

**Turing**Test, where a human judge viewing and interacting with a virtual world must distinguish between other humans interacting with the world and game bots ...

... The Church–

**Turing**thesis in recursion theory relies on a particular definition of the term algorithm ... Burgin argues that super-recursive algorithms, such as inductive

**Turing machines**disprove the Church–

**Turing**thesis ...

... The Annotated

**Turing**A Guided Tour Through Alan

**Turing**’s Historic Paper on Computability and the

**Turing Machine**is a book by Charles Petzold, published in 2008 by John Wiley Sons, Inc ... Petzold annotates Alan

**Turing**'s paper "On Computable Numbers, with an Application to the Entscheidungsproblem" ... The book takes readers sentence by sentence through

**Turing**'s paper, providing explanations, further examples, corrections, and biographical information ...

### Famous quotes containing the word machine:

“He is no more than the chief officer of the people, appointed by the laws, and circumscribed with definite powers, to assist in working the great *machine* of government erected for their use, and consequently subject to their superintendence.”

—Thomas Jefferson (1743–1826)