Two-State Turing Machine for Parenthesis Matching In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (symbols), you can reduce the number of states down to only 2.

I was looking for examples of different Turing Machines and a common example presented is the Parenthesis matcher/checker. Essentially it checks if a string of parentheses, e.g (()()()))()()() is balanced (the previous example would return 0 for unbalanced). 

Try as I may I can only get this to be a three state machine. I would love to know if anyone can reduce this down to the theoretical minimum of 2 and what their approach/states/symbols was!

Just to clarify, the parentheses are "sandwiched" between blank tape so in the above example
- - - - - - - (()()()))()()() - - - - - - - would be the input on the tape. The alphabet would include (,),1,0,-, and the *halt* state does not count as a state.

For reference the three state approach I have is as follows:
Description of states:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X


Transitions Listed as:

Action: State Symbol NewState WriteSymbol Motion




// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -


Forgive the informal way of writing all this down. I am still learning the theoretical constructs behind this.
Just a "source code" compendium of Raphael's answer: this a working version that uses the same trick (on state q1) and has tape alphabet:
_  ( ) [ { / \   (where $\_$ is the initial blank symbol) 

q0:  _ -&gt; accept  // accept on empty string and on balanced parenthesis
     ( -&gt; {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -&gt; reject  // reject if found unbalanced ")"
     \ -&gt; /,L,q0  // go left
     / -&gt; \,R,q0  // go right

q1:  ( -&gt; [,R,q1  // replace "(" with "[" and continue ...
     ) -&gt; /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -&gt; \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -&gt; reject  // no ")" found for the first "{", reject
     { -&gt; \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -&gt; /,L,q1  // go left
     / -&gt; \,R,q1  // go right


You can see it at work using a Turing machine online simulator; the source code is:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1


A final note: if you want to see how this technique can be pushed to the limit, read (and try to understand :-) the construction of the Universal Turing machine with 2 states and 18 symbols by Y. Rogozhin in "Small universal Turing machines"