Machine de Turing à deux états pour l'appariement des parenthèses

Au collège, nous avons appris la théorie du calcul en général et les machines de Turing plus spécifiquement. L'un des grands résultats théoriques est qu'au prix d'un alphabet potentiellement grand (symboles), vous pouvez réduire le nombre d'états à seulement 2.

Je cherchais des exemples de différentes machines de Turing et un exemple courant présenté est le matcher / vérificateur de parenthèses. Essentiellement, il vérifie si une chaîne de parenthèses, par exemple, (()()()))()()()est équilibrée (l'exemple précédent retournerait 0 pour asymétrique).

Essayez comme je peux, je ne peux obtenir que ceci soit une machine à trois états. J'aimerais savoir si quelqu'un peut réduire cela au minimum théorique de 2 et quelle était son approche / ses états / symboles!

Juste pour clarifier, les parenthèses sont "prises en sandwich" entre la bande vierge, donc dans l'exemple ci-dessus - - - - - - - (()()()))()()() - - - - - - -serait l'entrée sur la bande. L'alphabet comprendrait (, ), 1, 0, -et l' *halt*Etat ne compte pas comme un état.

Pour référence, l'approche à trois états que j'ai est la suivante: Description des états:

 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 répertoriées comme:

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 -

Pardonnez la manière informelle d'écrire tout cela. J'apprends toujours les constructions théoriques derrière cela.

Juste un recueil de "code source" de la réponse de Raphaël: c'est une version de travail qui utilise la même astuce (sur l'état q1) et a l'alphabet de la bande:
_ ( ) [ { / \ (où est le symbole vierge initial)$\_$

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

Vous pouvez le voir au travail en utilisant un simulateur en ligne de machine Turing ; le code source est:

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

Une dernière note: si vous voulez voir comment cette technique peut être poussée à la limite, lisez (et essayez de comprendre :-) la construction de la machine Universal Turing avec 2 états et 18 symboles par Y. Rogozhin dans "Small universal Turing" Machines"

Réponse stupide: votre résultat promet qu'il y a un machine de Turing universelle à deux états. Construisez n'importe quelle MT pour le langage Dyck, calculez son index et codez-le en dur dans la machine universelle.

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

• $q_0$

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

  $\hat{(}$$\hat{(}$$x$
  $\hat{)}$$\#$ première, boucle / reject¹ .

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

1. $x$