Máquina de Turing de dois estados para correspondência entre parênteses

Na faculdade, aprendemos mais sobre a teoria da computação em geral e sobre as máquinas de Turing. Um dos grandes resultados teóricos é que, ao custo de um alfabeto potencialmente grande (símbolos), você pode reduzir o número de estados para apenas 2.

Eu estava procurando exemplos de diferentes máquinas de Turing e um exemplo comum apresentado é o parênteses / verificador. Essencialmente, ele verifica se uma série de parênteses, por exemplo, (()()()))()()()está equilibrada (o exemplo anterior retornaria 0 para desequilibrado).

Por mais que eu tente, só consigo que isso seja uma máquina de três estados. Gostaria muito de saber se alguém pode reduzir isso para o mínimo teórico de 2 e qual foi a sua abordagem / estados / símbolos!

Apenas para esclarecer, os parênteses são "imprensados" entre a fita em branco; portanto, no exemplo acima, - - - - - - - (()()()))()()() - - - - - - -seria a entrada na fita. O alfabeto incluiria (, ), 1, 0, -, eo *halt*estado não conta como um estado.

Para referência, a abordagem de três estados que possuo é a seguinte: Descrição dos estados:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Transições Listadas como:

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 -

Perdoe a maneira informal de escrever tudo isso. Ainda estou aprendendo as construções teóricas por trás disso.

Apenas um compêndio de "código-fonte" da resposta de Raphael: esta é uma versão funcional que usa o mesmo truque (no estado q1) e tem um alfabeto de fita:
_ ( ) [ { / \ (onde é o símbolo em branco inicial)$\_$

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

Você pode vê-lo trabalhando usando um simulador on-line da máquina de Turing ; o código fonte é:

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

Uma observação final: se você quiser ver como essa técnica pode ser levada ao limite, leia (e tente entender :-) a construção da máquina Universal Turing com 2 estados e 18 símbolos de Y. Rogozhin em "Small Universal Turing máquinas "

Resposta idiota: seu resultado promete que existe uma máquina de Turing universal com dois estados. Construa qualquer TM para a linguagem Dyck, calcule seu índice e codifique-o na máquina universal.

$\{\#,(,),x\}$$\hat{a}$$a$

• $q_0$

  $)$$a$$\hat{a}$$)$$\hat{x}$
  $)$$\#$$\hat{x}$$q_1$

  $\hat{(}$$\hat{(}$$x$
  $\hat{)}$$\#$

• $q_1$$\hat{(}^+$$\hat{x}$$\#$$\hat{x}$

1. $x$