Combien de paires de supports sont suffisantes pour compléter Brainfuck Turing?

12

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

MilkyWay90
la source
1
"combien de paires de ces supports doivent être utilisées?" Pouvez-vous préciser "doivent être utilisés". Par exemple, que se passe-t-il si je demande à BrainF de compter jusqu'à 21000000 ?
John L.
@ Apass.Jack le nombre minimum de parenthèses
MilkyWay90
1
Oh, voulez-vous dire le nombre minimum de supports pour simuler une machine de Turing à états en fonction de n ? Quoi qu'il en soit, pouvez-vous donner un exemple non trivial aussi simple que possible? nn
John L.
1
@ Apass.Jack D'accord, je viens avec un programme buggy BF qui fonctionne pour une machine de Turing à un état
MilkyWay90
@ Apass.Jack Nevermind, c'est beaucoup trop dur pour moi. Fondamentalement, faites un interprète BF pour mon langage de programmation, Turing Machine But Way Pire , quand il n'utilise que deux symboles possibles (0 et 1) et supprimez complètement les E / S et l'aspect d'arrêt
MilkyWay90

Réponses:

9

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 (p1)/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

g(k)=4ck((rk1)mod(2c+1)),k=0,,2c1.

  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 }2cg(i)g(j)i,j{0,,2c1}
  2. g(k)mod(2c)0 , , 2 c - 1 prend une seule fois chaque valeur .0,,2c1

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{0,,c1}u ( x ) v ( x ) u(x) v(x)

u(x)=g(k1)<v(x)=g(k2) with u(x)v(x)x(modc)

Par la deuxième propriété de il y a exactement deux valeurs distinctes choisir.gk1,k2

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.02R

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 estH=v(h)u(h)NcN+1v((x+1)modc)u(x)x

initialisation ajustements[ >×(H+cN+1) [ <×c × H] <×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(c1)

  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 .0u(c1)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(c1)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)Hv(x)Hx

Soit le prochain compteur à visiter.y=((x+1)modc)

Le mouvement place le pointeur de bande sur une position qui est et non à gauche de .>×(H+cN+1)y(modc)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 .[ <×c c y v ( y ) u ( y )]cyv(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)2Rv(h)
  3. Ajustez la cellule de valeur du compteur suivant de (décrémentation du compteur).v((y+1)modc)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)yv(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.2R0

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.<×HH

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)]

Ørjan Johansen
la source
12

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.fxf(x,y)yf(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.xxf(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).ppqp(1+s+s2)sp2q2p2q2pp

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 à0i<p22i2q2p+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[>>>[ >×(2p1) [ <×(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 de2122q01s 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 de2p12x2p+2x12p2x1x2p2x+12p 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 modulo2p2x+12p2q112p2log2,p(r)+112r1rlog2,pp2paugmente 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).2p2pp

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)yxxy

  • 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 (100xyq10q 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=yf(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.

ais523
la source
Bon travail! Je vois que tu as travaillé là-dessus au TNB!
MilkyWay90
Je pense que vous devez avoir au moins p + 2. Lorsque s = p + 1, q vaut 1 de moins qu'une puissance de 2.
Ørjan Johansen
Je pense avoir trouvé un placement contre beaucoup plus simple (comme ne nécessitant pas la théorie des nombres premiers): 2p*2^i+2i.
Ørjan Johansen
@ ØrjanJohansen: D'accord, je pense avoir mentionné cette construction en #esoteric (quelque temps après avoir écrit ce post)? Tout ce dont vous avez réellement besoin est une règle de Golomb pour laquelle chaque élément est distinct modulo le nombre d'éléments, et il existe différentes façons de les construire (bien que trouver des optimaux soit difficile; le plus long que j'ai trouvé (via la force brute) est [0, 1, 3, 7, 20, 32, 42, 53, 58]pour p = 9).
ais523
Oh, vous l'avez fait (juste avant de dire que mon cerveau a refusé d'être en mode mathématique, alors voici mon excuse: P). Je suppose que j'ai alors découvert que k = 0 était suffisant. Je pense que la construction Erdős – Turan_construction de Wikipédia en donne une de croissance polynomiale (et probablement O () - optimale?) Si vous n'utilisez que la première moitié des éléments (l'autre moitié se répète (mod p)).
Ørjan Johansen