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
-, 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.