9
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Apr 5 '13 at 8:16

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Are we allowed to use a larger alphabet? $\endgroup$ – Raphael Apr 5 '13 at 9:26
  • $\begingroup$ @Raphael According to the theoretical result, one can exchange states for alphabet and vice versa. So reducing the states to two means you will most likely have to use a larger alphabet. So yes, the short answer is The alphabet can be as large as desired $\endgroup$ – Four_FUN Apr 5 '13 at 9:32
  • $\begingroup$ I think, in a two tape TM, this can be done with no extra symbols and. $\endgroup$ – Karolis Juodelė Apr 5 '13 at 9:51
  • $\begingroup$ @Four_FUN are you from MIT? $\endgroup$ – user42419 Nov 15 '15 at 9:13
8
$\begingroup$

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:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

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

$\endgroup$
  • $\begingroup$ Didn't we decide that answers presenting only source code are no good for Computer Science? ;) $\endgroup$ – Raphael Apr 5 '13 at 13:57
  • 1
    $\begingroup$ @Raphael: I agree with you, but mine can be viewed just like an addendum to yours (that seems fine, even if I didn't check the details). I'll add a note about this. $\endgroup$ – Vor Apr 5 '13 at 14:01
  • 1
    $\begingroup$ @Raphael: I coded it just for fun trying to minimize the tape symbols, and it "seems" :-) to work so I decided to post it. $\endgroup$ – Vor Apr 5 '13 at 14:03
  • $\begingroup$ @Vor. Thank you very much for your additional input into this problem. All this tells me is that I need more practice in this stuff. Thank you for posting your source code nonethless, even though the theory was what I was after. $\endgroup$ – Four_FUN Apr 5 '13 at 18:42
  • 1
    $\begingroup$ @Four_FUN: the Rogozhin Universal TM (2,18) is a standard Turing machine (i.e. apart from the input its initial tape contains only blank symbols) that simulates an arbitrary 2-tag system (which is a universal model). The 2 state 3 symbol one is a weakly Turing machine (the initial tape needs to be filled with an infinite sequence of a pattern), and the universality is "reached" simulating the cellular automata Rule 110 (which has been proved to be Turing complete). There is a (claimed?) proof that a standard TM(2,3) cannot be Turing complete. $\endgroup$ – Vor Apr 5 '13 at 21:12
7
$\begingroup$

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.


  1. 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.
$\endgroup$
  • $\begingroup$ If you don't mind me asking, how exactly does my solution promise a universal TM with two states? (very smart solution btw. thnak you for your input) $\endgroup$ – Four_FUN Apr 5 '13 at 18:46
  • 1
    $\begingroup$ @Four_FUN: because you say in your question: "... 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..." ... so you can also pick an arbitrary Universal Turing machine and reduce the number of states to only 2. And if you do some experiments you'll also realize that it's not hard to make an automatic procedure that converts an arbitrary TM to an equivalent 2 state TM (if you don't care about minimization of the number of alphabet symbols). $\endgroup$ – Vor Apr 5 '13 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.