Máquina de Turing de dos estados para emparejar paréntesis

En la universidad hemos estado aprendiendo sobre la teoría de la computación en general y las máquinas de Turing más específicamente. Uno de los grandes resultados teóricos es que, a costa de un alfabeto (símbolos) potencialmente grande, puede reducir el número de estados a solo 2.

Estaba buscando ejemplos de diferentes máquinas de Turing y un ejemplo común presentado es el comparador / corrector de paréntesis. Básicamente, comprueba si una cadena de paréntesis, por ejemplo, (()()()))()()()está equilibrada (el ejemplo anterior devolvería 0 para desequilibrado).

Por más que lo intente, solo puedo lograr que sea una máquina de tres estados. ¡Me encantaría saber si alguien puede reducir esto al mínimo teórico de 2 y cuál fue su enfoque / estados / símbolos!

Solo para aclarar, los paréntesis están "intercalados" entre la cinta en blanco, por lo que en el ejemplo anterior - - - - - - - (()()()))()()() - - - - - - -sería la entrada en la cinta. El alfabeto incluiría (, ), 1, 0, -, y el *halt*estado no cuenta como un estado.

Como referencia, el enfoque de tres estados que tengo es el siguiente: Descripción de los 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

Transiciones enumeradas 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 -

Perdona la forma informal de escribir todo esto. Todavía estoy aprendiendo las construcciones teóricas detrás de esto.

Solo un compendio de "código fuente" de la respuesta de Raphael: esta es una versión funcional que usa el mismo truco (en el estado q1) y tiene alfabeto de cinta:
_ ( ) [ { / \ (donde es el símbolo inicial en blanco)$\_$

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

Puede verlo en funcionamiento utilizando un simulador en línea de la máquina Turing ; el código fuente es:

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

Una nota final: si desea ver cómo esta técnica puede llevarse al límite, lea (y trate de comprender :-) la construcción de la máquina Universal Turing con 2 estados y 18 símbolos por Y. Rogozhin en "Pequeño Turing universal máquinas"

Respuesta tonta: su resultado promete que hay una máquina universal de Turing con dos estados. Construya cualquier TM para el lenguaje Dyck, calcule su índice y codifíquelo en la máquina universal.

Pero eso, por supuesto, no es muy satisfactorio. Su enfoque en realidad funciona si "engaña" la diferencia entre moverse hacia la izquierda y hacia la derecha al unir pares de paréntesis en una extensión del alfabeto. Necesitamos y versiones marcadas de todos los símbolos .un$\{\#,(,),x\}$$\hat{a}$$a$

• El estado inicial funciona de la siguiente manera.$q_0$

  Cuando encuentre símbolos sin marcar, muévase hacia la derecha hasta encontrar el primero . Mientras lo hace, sobrescriba todos los símbolos con . Sobrescriba lo encontrado con . Si no hay , es decir, presionamos el símbolo de espacio , lo sobrescribimos con y a .Un una ) x ) $)$$a$$\hat{a}$$)$$\hat{x}$
  $)$$\#$ q$\hat{x}$$q_1$

  Cuando encuentre símbolos marcados, muévase hacia la izquierda hasta encontrar el primer , sobrescribiendo todos los símbolos pasados ​​(marcados) con sus variantes sin marcar. Sobrescriba el con . Si encontramos un o primero, bucle / rechazar¹. $\hat{(}$$\hat{(}$)$x$
  $\hat{)}$$\#$

• En , verificamos que todo haya coincidido; aún puede haber prefijos de la forma en la cinta. Es decir, moverse hacia la izquierda siempre que encontremos . Si así encontramos , acepte; si encontramos alguno otro símbolo pero primero, bucle / rechazar.( + $q_1$$\hat{(}^+$$\hat{x}$$\#$$\hat{x}$

1. Esto es correcto ya que la máquina coincide de adentro hacia afuera; en una entrada legal, solo hay entre el par de paréntesis que se está haciendo coincidir actualmente.$x$