Brainfuck est un langage de programmation complet de Turing qui n'utilise que 8 symboles (6 si vous ignorez les E / S).

Les deux plus notables qui l'ont poussé à l'exhaustivité de Turing sont [et ], essentiellement, le label et goto de Brainfuck.

Normalement, les programmes de Brainfuck utilisent plusieurs ensembles de [], mais je me demandais exactement combien de paires de ces supports doivent être utilisées pour rendre Brainfuck Turing complet?

Plus simplement, quelle est la quantité minimale de supports dont vous auriez besoin pour simuler une machine de Turing à n états (indiquez le nombre de supports pour les machines de Turing à 1, 2 et trois états)?

Remarques:

Nous supposons une bande infinie et aucune limite de calcul.

C'est une machine de Turing à 2 symboles

Il s'agit d'un développement supplémentaire de la réponse de @ ais523 , la réduisant à seulement deux ensembles de supports, et utilisant également un placement de cellule plus compact basé sur la théorie de la règle de Golomb. ais523 a créé un compilateur pour cette construction , ainsi que cette session TIO montrant un exemple de programme BF résultant exécuté avec le suivi de débogage des compteurs TWM.

Comme l'original, cela commence par un programme dans The Waterfall Model , avec quelques restrictions qui ne perdent pas la généralité:

1. Tous les compteurs ont la même valeur de réinitialisation automatique $R$ ; c'est-à-dire que la carte de déclenchement TWM $f$ a la propriété $f(x,x)=R$ pour tous les $x$ .
2. Il y a un seul compteur d'arrêt $h$ .
3. Le nombre $c$ de compteurs est $(p-1)/2$ pour un nombre premier $p$ .

Règle de Golomb

Nous combinons la construction Erdős – Turán avec la fonction de permutation d'un tableau Welch – Costas afin d'obtenir une règle de Golomb avec les propriétés nécessaires.

(Je suis sûr que cette construction combinée ne peut pas être une nouvelle idée, mais nous venons de trouver et d'assembler ces deux pièces de Wikipedia.)

Soit $r$ une racine primitive de $p=2c+1$ . Définissez la fonction

1. $g$ est une règle de Golomb d'ordre . C'est-à-dire que la différence est unique pour chaque paire de nombres distincts .2 c g ( i ) - g ( j ) i , j ∈ { 0 , … , 2 c - 1 }$2c$$g(i)-g(j)$$i,j \in \{0,\ldots,2c-1\}$
2. $g(k)\bmod(2c)$0 , … , 2 c - 1 prend une seule fois chaque valeur .$0,\ldots,2c-1$

Structure du ruban

Pour chaque compteur TWM , nous attribuons deux positions de cellule de bande BF, une cellule de secours et une cellule de valeur :$x\in \{0,\ldots,c-1\}$u ( x ) v ( x ) $u(x)$ $v(x)$

Par la deuxième propriété de il y a exactement deux valeurs distinctes choisir.$g$$k_1,k_2$

Le contenu d'une cellule de secours sera la plupart du temps maintenu à , sauf lorsque son compteur vient d'être visité, lorsqu'il sera à , deux fois la valeur de réinitialisation automatique du compteur. Une cellule de valeur sera maintenue à deux fois la valeur du compteur TWM ​​correspondant.$0$$2R$

Toutes les autres cellules qui peuvent être atteintes par l'exécution du programme BF (un nombre fini) seront conservées à des valeurs impaires, afin qu'elles testent toujours comme non nulles. Après l'initialisation, cela est automatique car tous les ajustements de cellule sont effectués en quantités égales.

Si vous le souhaitez, toutes les positions des cellules peuvent être décalées vers la droite d'une constante afin d'éviter de se déplacer vers la gauche de la position initiale de la bande BF.

Structure du programme BF

Soit la distance entre la valeur du compteur d'arrêt et les cellules de repli, et soit un nombre suffisamment grand pour que pour tous les compteurs . Ensuite, la structure de base du programme BF est$H = v(h)-u(h)$$N$$cN+1 \geq v((x+1)\bmod c) - u(x)$$x$

initialisation ajustements[ >$\times (H+cN+1)$ [ <$\times c$ × H] <$\times H$ ]

Initialisation

La phase d' initialisation met toutes les cellules accessibles par le programme à leurs valeurs initiales, dans un état comme si le dernier compteur venait d'être visité et que la cellule juste active était sa cellule de secours :$u(c-1)$

1. Les cellules de valeur sont initialisées à deux fois le contenu initial du compteur TWM ​​correspondant, sauf que le compteur est pré-décrémenté.$0$
2. Les cellules de repli sont définies sur , à l'exception de la cellule , qui est définie sur .$0$$u(c-1)$$2R$
3. Toutes les autres cellules accessibles par le programme (un nombre fini) sont définies sur .$1$

Ensuite, le pointeur de bande est déplacé vers la position (une cellule toujours non nulle) avant d'atteindre le premier programme .$u(c-1)-H$[

Début de la boucle extérieure

Au début d'une itération de la boucle externe, le pointeur de bande sera à ou pour un compteur .$u(x)-H$$v(x)-H$$x$

Soit le prochain compteur à visiter.$y=((x+1)\bmod c)$

Le mouvement place le pointeur de bande sur une position qui est et non à gauche de .>$\times (H+cN+1)$$\equiv y\pmod c$$v(y)$

La boucle interne recherche maintenant vers la gauche aux étapes de une cellule nulle. Si le compteur est nul, il s'arrêtera à la cellule de valeur (zéro) ; sinon, il trouvera la cellule de repli .[ <$\times c$ c y v ( y ) u ( y )]$c$$y$$v(y)$$u(y)$

La cellule trouvée devient la nouvelle cellule active .

Ajustements

La phase d' ajustement ajuste diverses cellules sur la bande en fonction de leur position par rapport à la cellule active. Cette section ne contient que des +-><commandes et ces ajustements se produisent donc sans condition. Cependant, comme toutes les cellules liées au compteur sont dans un modèle de règle de Golomb, tous les ajustements qui ne sont pas appropriés pour la cellule active actuelle manqueront toutes les cellules importantes et ajusteront à la place certaines cellules non pertinentes (tout en le gardant étrange).

Un code distinct doit donc être inclus dans le programme pour chaque paire requise possible de cellule active et ajustée, à l' exception de l'auto-ajustement d'une cellule active qui, parce que l'ajustement est basé uniquement sur la position relative, doit être partagée entre toutes.

Les ajustements requis sont:

1. Ajustez la cellule de secours du compteur précédent de .$u(x)$$-2R$
2. Ajustez la cellule de repli du compteur actuel de , sauf si la cellule active actuelle est et que nous devons donc nous arrêter.$u(y)$$2R$$v(h)$
3. Ajustez la cellule de valeur du compteur suivant de (décrémentation du compteur).$v((y+1)\bmod c)$$-2$
4. Lorsque la cellule active est une cellule de valeur (de sorte que le compteur a atteint zéro), ajustez toutes les cellules de valeur de partir de la carte de déclenchement TWM. lui-même est ajusté de .$v(y)$$y$$v(z)$$2f(y,z)$$v(y)$$2R$

Les premier et deuxième ajustements ci - dessus sont rendues nécessaires par le fait que toutes les cellules actives doivent régler eux - mêmes par la même valeur, qui est pour les cellules de valeur, et donc aussi pour les cellules de secours. Cela nécessite de préparer et de nettoyer les cellules de secours pour s'assurer qu'elles reviennent à dans les branches de valeur et de secours.$2R$$0$

Fin de la boucle extérieure

Le mouvement représente qu'à la fin de la phase de réglage, le pointeur de bande est déplacé à gauche de la cellule active.<$\times H$$H$

Pour toutes les cellules actives autres que la cellule de valeur du compteur d'arrêt , il s'agit d'une cellule non pertinente, donc impaire et non nulle, et la boucle externe continue pour une autre itération.$v(h)$

Pour , le pointeur est placé à la place sur sa cellule de repli correspondante , pour laquelle nous avons fait une exception ci-dessus pour le maintenir à zéro, et donc le programme se termine par la finale et s'arrête.$v(h)$$u(h)$]

Je ne suis pas sûr à 100% qu'il est impossible de le faire avec deux ensembles de supports. Cependant, si les cellules de la bande BF autorisent des valeurs illimitées, trois ensembles de crochets suffisent. (Par souci de simplicité, je suppose également que nous pouvons déplacer la tête de bande vers la gauche au-delà de son point de départ, bien que parce que cette construction n'utilise qu'une région finie de la bande, nous pourrions lever cette restriction en ajoutant suffisamment de >commandes au début de la programme.) La construction ci-dessous nécessite de supposer la conjecture d'Artinpouvoir compiler des programmes arbitrairement volumineux; Cependant, même si la conjecture d'Artin est fausse, il sera toujours possible de montrer Turing-complétude indirectement en traduisant un interprète pour une langue Turing-complete en BF en utilisant la construction ci-dessous, et en exécutant des programmes arbitraires en les donnant comme entrée à cet interprète.

Le langage complet de Turing que nous compilons en BF illimité est le modèle Waterfall , qui est l'un des modèles de calcul connus les plus simples. Pour les personnes qui ne le savent pas déjà, il se compose d'un certain nombre de compteurs (et de valeurs initiales pour eux), et d'une fonction de paires de compteurs en entiers; l'exécution du programme consiste à soustraire à plusieurs reprises 1 de chaque compteur, puis si un compteur est 0, ajouter à chaque compteur (le programme est écrit de telle manière que cela n'arrive jamais à plusieurs compteurs simultanément). Il y a une preuve d'exhaustivité de Turing pour cette langue derrière mon lien. Sans perte de généralité, nous supposerons que tous les compteurs ont la même valeur de réinitialisation automatique (c.-à-d.$f$$x$$f(x,y)$$y$$f(x,x)$ est le même pour tous les ); c'est une hypothèse sûre car pour tout spécifique , l'ajout de la même constante à chaque ne changera pas le comportement du programme.$x$$x$$f(x,y)$

Soit le nombre de compteurs; sans perte de généralité (en supposant la conjecture d'Artin), supposons que a une racine primitive 2. Soit soit , où est la puissance la plus faible de 2 supérieure à . Sans perte de généralité, sera inférieur à ( est borné polynomialement, croît exponentiellement, donc tout suffisamment grand fonctionnera).$p$$p$$q$$p(1+s+s^2)$$s$$p$$2q$$2^p$$2q$$2^p$$p$

La disposition des bandes est la suivante: nous numérotons chaque compteur avec un entier (et sans perte de généralité, nous supposons qu'il y a un seul compteur d'arrêt et nous le numérotons ). La valeur de la plupart des compteurs est stockée sur la cellule de bande , à l'exception du compteur 0, qui est stocké sur la cellule de bande . Pour chaque cellule de bande impaire de la cellule -1 à$0 \leq i < p$$2$$2^i$$2q$$2^{p+1}+2p+1$, cette cellule de bande contient toujours 1, sauf si elle se trouve immédiatement à gauche d'un compteur, auquel cas elle contient toujours 0. Les cellules de bande de nombre pair qui ne sont pas utilisées comme compteurs ont des valeurs non pertinentes (qui peuvent ou non être 0 ); et les cellules de bande impaires en dehors de la plage indiquée ont également des valeurs non pertinentes. Notez que la définition de la bande dans un état initial approprié nécessite d'initialiser uniquement un nombre fini d'éléments de bande à des valeurs constantes, ce qui signifie que nous pouvons le faire avec une séquence d' <>+-instructions (en fait, seules >+sont nécessaires), donc pas de crochets. À la fin de cette initialisation, nous déplaçons le pointeur de bande sur la cellule -1.

La forme générale de notre programme ressemblera à ceci:

initialisation ajustement[>>>[ >$\times(2^p-1)$ [ <$\times(2p)$ ]>-] <<<]

L'initialisation met la bande dans la forme attendue et le pointeur sur la cellule -1. Ce n'est pas la cellule à gauche d'un compteur (0 n'est pas une puissance de 2), donc il a la valeur 1, et nous entrons dans la boucle. L'invariant de boucle pour cette boucle la plus externe est que le pointeur de bande est (au début et à la fin de chaque itération de boucle) trois cellules à gauche d'un compteur; on peut voir que la boucle ne sortira donc que si nous sommes trois cellules à gauche du compteur 2 (chaque autre compteur a un 1 trois cellules à sa gauche, car avoir un 0 impliquerait que les positions de bande de deux compteurs étaient séparés par 2 cellules; les deux seules puissances de 2 qui diffèrent par 2 sont et , et la représentation binaire de passe de chaînes de s à chaînes de$2^1$$2^2$$q$$0$$1$s ou vice versa au moins quatre fois et ne peut donc pas être à 1 de la puissance de 2).

La deuxième boucle boucle à plusieurs reprises sur les compteurs, en les décrémentant. L'invariant de boucle est que le pointeur de bande pointe toujours vers un compteur; ainsi la boucle se terminera lorsqu'un compteur deviendra 0. La décrémentation est juste -; la façon dont nous passons d'un compteur à l'autre est plus complexe. L'idée de base est que le déplacement de espaces vers la droite de nous placera sur une cellule de nombre impair , qui est à droite de n'importe quel compteur ( est le dernier compteur, est positif car est positif); modulo , cette valeur est congruente (selon le petit théorème de Fermat) . La boucle la plus intérieure se déplace à plusieurs reprises vers la gauche de$2^p-1$$2^x$$2^p+2^x-1$$2^p$$2^x-1$$x$$2p$$2^x+1$$2p$ espaces, ne changeant pas non plus l'indice de la cellule de bande modulo , et doit finalement trouver la cellule congruente à modulo qui a la valeur (qui sera la cellule à gauche d'un compteur); en raison de notre exigence de racine primitive, il y a exactement une cellule de ce type ( est congru à modulo , et est congru à pour tout autre , où est le logarithme discret de base 2 modulo ). De plus, on peut voir que la position du pointeur de bande modulo$2p$$2^x+1$$2p$$2q-1$$-1$$2p$$2^{\log_{2,p}(r)+1}-1$$2r-1$$r$$\log_{2,p}$$p$$2p$augmente de chaque fois autour de la boucle du milieu. Ainsi, le pointeur de bande doit alterner entre tous les compteurs (dans l'ordre de leurs valeurs modulo ). Ainsi, à chaque itération, nous diminuons chaque compteur (au besoin). Si la boucle se brise à mi-chemin d'une itération, nous reprendrons la diminution lorsque nous entrerons à nouveau dans la boucle (car le reste de la boucle la plus externe n'apporte aucun changement net à la position du pointeur de bande).$2$$p$$2p$$p$

Lorsqu'un compteur atteint 0, la boucle du milieu se rompt, nous amenant au code "d'ajustement". Il s'agit simplement d'un encodage de ; pour chaque paire , on ajoute à l'élément de bande qui est la même distance gauche / droite du pointeur de la bande en cours comme compteur « emplacement de la bande S est la gauche / droite du compteur » s l'emplacement de la bande (puis retire le pointeur de bande à l'endroit où il a commencé). Chaque fois que , cette distance se révèle unique:$f$$(x,y)$$f(x,y)$$y$$x$$x\neq y$

• La différence entre deux puissances de 2 est un nombre binaire composé d'une chaîne de 1 ou plusieurs s suivie d'une chaîne de 0 ou plusieurs s (avec les valeurs de position du début du nombre et du début de la chaîne , en fonction du plus grand et du plus petit respectivement de et ); toutes ces différences sont donc distinctes. * Quant à la différence d'une puissance de 2 et , elle doit contenir au moins deux transitions entre des chaînes de s et s ($1$$0$$0$$x$$y$$q$$1$$0$$q$ contient au moins quatre de ces transitions, la soustraction ne peut supprimer que 2), est donc distincte de toutes les différences de deux puissances de deux, et ces différences sont évidemment également distinctes les unes des autres.

Pour , nous constatons évidemment que la distance parcourue est de 0. Mais parce que tous les sont égaux, nous pouvons simplement l'utiliser comme ajustement pour la cellule courante. Et on peut voir que le code d'ajustement implémente ainsi l'effet "lorsqu'un compteur atteint 0" pour chaque compteur; toutes les cellules qui représentent réellement les compteurs seront ajustées du montant correct, et tous les autres ajustements affecteront les cellules paires sans compteur (la différence entre deux nombres pairs est paire), ce qui n'a aucun effet sur le comportement du programme.$x=y$$f(x,y)$

Ainsi, nous avons maintenant une compilation de travail de tout programme dans The Waterfall Model to BF (y compris le comportement d'arrêt, mais n'incluant pas les E / S, ce qui n'est pas nécessaire pour la complétude de Turing) en utilisant seulement trois paires de crochets, et donc trois paires des parenthèses sont suffisantes pour Turing-complétude.