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: ),(,XTransitions Listed as:Action: State Symbol NewState WriteSymbol Motion// Termination behaviorAction: s2 - *halt* 0  -Action: s1 -  s3    -  r//Transitions of TMAction: s1 (  s1  (   lAction: s1 )  s2  X  rAction: s1 X  s1  X  lAction: s2 ( s1 X  lAction: s2 X  s2 X rAction: s3 (  *halt* 0 -Action: s3 X  s3     X rAction: s3 -  *halt* 1 -Forgive the informal way of writing all this down. I am still learning the theoretical constructs behind this.
Two-State Turing Machine for Parenthesis Matching
turing machines;context free;parsers