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.

Dumb answer: your result promises that there is a universal Turing machine with two states.
Construct any TM for the Dyck language, compute its index and hardcode it into the universal
machine.

But that's of course not very satisfying. Your approach actually works if you "trick" the
difference between moving left and moving right while matching pairs of parenthesis into an
extension of the alphabet. We need $\{\#,(,),x\}$ and marked versions $\hat{a}$ of all
symbols $a$.

-
The initial state $q_0$ works as follows.

When finding unmarked symbols, move to the right until the first $)$ is found.
While doing so, overwrite all symbols $a$ with $\hat{a}$.
Overwrite the found $)$ with $\hat{x}$.

If there is no $)$, i.e. we hit the gap symbol $\#$, overwrite it with $\hat{x}$
and switch to $q_1$.

When finding marked symbols, move to the left until the first $\hat{(}$ is found,
overwriting all passed (marked) symbols with their unmarked variants.
Overwrite the found $\hat{(}$ with $x$.

If we find a $\hat{)}$ or $\#$ first, loop/reject¹.

-
In $q_1$, we check that everything has been matched; there may still be prefixes
of the form $\hat{(}^+$ on the tape. That is, move to the left as long as we
finde $\hat{x}$. If we thus find $\#$, accept; if we find any other symbol but
$\hat{x}$ first, loop/reject.

• This is correct since the machine matches inside-out; in a legal input, there

are only $x$ between the pair of parentheses currently being matched.

StackExchange Computer Science Q#11044, answer score: 8