Brainfuck ist eine vollständige Programmiersprache von Turing, die nur 8 Symbole verwendet (6, wenn Sie E / A ignorieren).

Die zwei bemerkenswertesten, die es zur Vollständigkeit bringen, sind [und ]im Wesentlichen Brainfucks Label und goto.

Normalerweise verwenden Programme in Brainfuck mehrere Sätze von [], aber ich habe mich gefragt, wie viele Paare dieser Klammern verwendet werden müssen, um Brainfuck Turing zu vervollständigen?

Einfacher ausgedrückt, wie viele Klammern würden Sie am wenigsten benötigen, um eine Turingmaschine mit n-Status zu simulieren (Geben Sie die Anzahl der Klammern für Turingmaschinen mit 1, 2 und 3 Status an)?

Anmerkungen:

Wir gehen von einem unendlichen Band und keinen rechnerischen Grenzen aus.

Es ist eine Turingmaschine mit 2 Symbolen

Dies ist eine Weiterentwicklung der Antwort von @ ais523 , die auf nur zwei Sätze von Klammern reduziert wurde und außerdem eine kompaktere Zellenplatzierung verwendet , die auf der Golomb-Lineal-Theorie basiert. ais523 hat einen Compiler für diese Konstruktion sowie für diese TIO-Sitzung erstellt , der ein Beispiel für ein BF-Programm zeigt, das mit Debug-Tracing der TWM-Zähler ausgeführt wird.

Dies beginnt wie das Original mit einem Programm in The Waterfall Model , mit einigen Einschränkungen, die nicht an Allgemeingültigkeit verlieren:

1. Alle Zähler haben den gleichen Rückstellwert $R$ ; Das heißt, die TWM-Trigger-Map $f$ hat die Eigenschaft, dass $f(x,x)=R$ für alle $x$ .
2. Es gibt einen einzelnen Haltezähler $h$ .
3. Die Anzahl $c$ der Zähler ist $(p-1)/2$ für eine Primzahl $p$ .

Golomb Herrscher

Wir kombinieren die Erdős-Turán-Konstruktion mit der Permutationsfunktion eines Welch-Costas-Arrays , um ein Golomb-Lineal mit den erforderlichen Eigenschaften zu erhalten.

(Ich bin mir sicher, dass diese kombinierte Konstruktion keine neue Idee sein kann, aber wir haben gerade diese beiden Teile aus Wikipedia gefunden und zusammengefügt.)

Sei $r$ eine Urwurzel von $p=2c+1$ . Definieren Sie die Funktion

1. $g$ ist einGolomb-Linealder Ordnung$2c$ . Das heißt, der Unterschied$g(i)-g(j)$ ist für jedes Paar unterschiedlicher Zahlen$i,j \in \{0,\ldots,2c-1\}$ eindeutig.
2. $g(k)\bmod(2c)$ nimmt jeden Wert$0,\ldots,2c-1$ genau einmal an.

Bandstruktur

Für jeden TWM-Zähler $x\in \{0,\ldots,c-1\}$ weisen wir zwei BF-Bandzellenpositionen zu, eineErsatzzelle $u(x)$ und eineWertzelle $v(x)$ :

Durch die zweite Eigenschaft von $g$ stehen genau zwei verschiedene $k_1,k_2$ -Werte zur Auswahl.

Der Inhalt einer Fallback-Zelle wird die meiste Zeit auf $0$ , es sei denn, der Zähler wurde gerade aufgesucht, und bei $2R$ wird der doppelte Wert für die Selbstzurücksetzung des Zählers erreicht. Eine Wertzelle wird auf dem doppelten Wert des entsprechenden TWM-Zählers gehalten.

Alle anderen Zellen, die von der BF-Programmausführung erreicht werden können (eine endliche Zahl), werden auf ungeraden Werten gehalten, sodass sie immer als ungleich Null getestet werden. Nach der Initialisierung erfolgt dies automatisch, da alle Zelleneinstellungen in geraden Mengen vorgenommen werden.

Falls gewünscht, können alle Zellenpositionen um eine Konstante nach rechts verschoben werden, um zu vermeiden, dass die ursprüngliche Position des BF-Bandes nach links verschoben wird.

BF Programmstruktur

Sei $H = v(h)-u(h)$ der Abstand zwischen dem Wert des Stoppzählers und den Fallback-Zellen, und sei $N$ eine Zahl, die groß genug ist, dass $cN+1 \geq v((x+1)\bmod c) - u(x)$ für alle Zähler$x$ . Dann ist die grundlegende BF-Programmstruktur

Initialisierung [ >$\times (H+cN+1)$ [ <$\times c$ ] Anpassungen <$\times H$ ]

Initialisierung

In der Initialisierungsphase werden alle vom Programm erreichbaren Zellen auf ihre Anfangswerte gesetzt, und zwar in einem Zustand, in dem der letzte Zähler gerade besucht wurde und die gerade aktive Zelle die Ersatzzelle $u(c-1)$ :

1. Wertzellen werden auf den doppelten Anfangsinhalt des entsprechenden TWM-Zählers initialisiert, mit der Ausnahme, dass der Zähler $0$ vorab dekrementiert wird.
2. Fallback-Zellen sind auf gesetzt $0$ , mit Ausnahme der Zelle$u(c-1)$ , die auf$2R$ .
3. Alle anderen vom Programm erreichbaren Zellen (eine endliche Zahl) werden auf $1$ .

Dann wird der Bandzeiger auf die Position $u(c-1)-H$ (eine Zelle, die immer nicht Null ist) bewegt, bevor wir das erste Programm erreichen [.

Beginn der äußeren Schleife

Zu Beginn einer Iteration der äußeren Schleife befindet sich der Bandzeiger entweder auf $u(x)-H$ oder $v(x)-H$ für einen Zähler $x$ .

Lassen $y=((x+1)\bmod c)$ der nächste zu besuchende Zähler.

Die Bewegung >$\times (H+cN+1)$ legtdas Band Zeiger auf eine Positiondie ist$\equiv y\pmod c$ und nicht links von$v(y)$ .

Die innere Schleife [ <$\times c$ ] sucht nun in Schritten von $c$ nach links nach einer Nullzelle. Wenn der Zähler $y$ Null ist, stoppt er bei der (Null-) Wertzelle $v(y)$ . Andernfalls wird die Fallback-Zelle$u(y)$ .

Welche Zelle gefunden wird, wird zur neuen aktiven Zelle.

Anpassungen

In der Anpassungsphase werden verschiedene Zellen auf dem Band basierend auf ihrer Position relativ zur aktiven Zelle angepasst. Dieser Abschnitt enthält nur +-><Befehle, daher erfolgen diese Anpassungen bedingungslos. Da sich jedoch alle mit Zählern verbundenen Zellen in einem Golomb-Linealmuster befinden, werden bei Anpassungen, die für die derzeit aktive Zelle nicht geeignet sind, alle wichtigen Zellen übersehen und stattdessen einige irrelevante Zellen angepasst (wobei sie ungerade bleiben).

Daher muss für jedes möglicherweise erforderliche Paar von aktiven und angepassten Zellen ein separater Code in das Programm aufgenommen werden, mit Ausnahme der Selbsteinstellung einer aktiven Zelle, die, da die Einstellung ausschließlich auf der relativen Position basiert, von allen geteilt werden muss.

Die erforderlichen Anpassungen sind:

1. Passen Sie die Fallback-Zelle u des vorherigen Zählers an ( x$u(x)$um$-2R$ .
2. Passen Sie die Fallback-Zelle $u(y)$ des aktuellen Zählers um $2R$ . denn, die derzeit aktive Zelle ist $v(h)$ und wir sollten anhalten.
3. Passen Sie den Wert der Zelle v ( ( y + 1 ) mod c des nächsten Zählers an$v((y+1)\bmod c)$ von$-2$ (Dekrementieren des Zählers).
4. Wenn die aktive Zelle eine Wertezelle $v(y)$ (der Zähler $y$ hat also Null erreicht), passen Sie alle Wertezellen $v(z)$ über die TWM-Triggerzuordnung um $2f(y,z)$ an. $v(y)$ selbst wird um $2R$ angepasst .

Die obigen ersten und zweiten Anpassungen werden dadurch erforderlich, dass sich alle aktiven Zellen um denselben Wert anpassen müssen , d. H$2R$für Wertzellen und damit auch für Fallback-Zellen 2 R beträgt. Dazu müssen die Fallback-Zellen vorbereitet und bereinigt werden, um sicherzustellen, dass siesowohl im Wert- als auch im Fallback-Zweigauf$0$ zurückkehren.

Ende der äußeren Schleife

Die Bewegung <$\times H$ stellt dar, dass am Ende der Anpassungsphase der Bandzeiger um$H$ Stellen links von der aktiven Zellebewegtwird.

Für alle aktiven Zellen andere als die Anhaltewertzelle des Zählers$v(h)$ ,ist dies ein irrelevantes Zelle, und so ungerade und ungleich Null, und die äußere Schleifefortgesetzt fürweitere Iteration.

Für $v(h)$ wird der Zeiger stattdessen auf die entsprechende Fallback-Zelle gesetzt. $u(h)$ , für die wir oben eine Ausnahme gemacht haben, um sie auf Null zu halten, und daher wird das Programm durch das Ende ]und die Unterbrechungen beendet.

Ich bin mir nicht hundertprozentig sicher, dass es unmöglich ist, dies mit zwei Sätzen von Klammern zu tun. Wenn die Zellen des BF-Bands jedoch unbegrenzte Werte zulassen, reichen drei Sätze von Klammern aus. (Der Einfachheit halber gehe ich auch davon aus, dass wir den Bandkopf über seinen Startpunkt hinaus nach links bewegen können. Da diese Konstruktion jedoch nur einen begrenzten Bereich des Bandes verwendet, können wir diese Einschränkung aufheben, indem wir >zu Beginn des Bandes ausreichend viele Befehle hinzufügen Programm.) Die folgende Konstruktion erfordert die Annahme von Artins Vermutungin der Lage zu sein, beliebig große Programme zu kompilieren; Selbst wenn Artins Vermutung falsch ist, ist es dennoch möglich, die Turing-Vollständigkeit indirekt zu zeigen, indem ein Interpreter für eine Turing-vollständige Sprache mit der folgenden Konstruktion in BF übersetzt und beliebige Programme ausgeführt werden, indem sie als Eingabe für diesen Interpreter verwendet werden.

Die Turing-complete-Sprache, die wir zu unbegrenztem BF kompilieren, ist das Waterfall-Modell , eines der einfachsten bekannten Rechenmodelle. Für Leute, die es noch nicht kennen, besteht es aus einer Anzahl von Zählern (und Anfangswerten für sie) und einer Funktion $f$ von Paaren von Zählern zu ganzen Zahlen; Programmausführung besteht aus 1 wiederholt von jedem Zähler subtrahiert, dann , wenn irgendein Zähler $x$ 0 ist , das Hinzufügen $f(x,y)$ für jeden Zähler$y$(Das Programm ist so geschrieben, dass dies niemals bei mehreren Zählern gleichzeitig auftritt.) Es gibt einen Turing-Vollständigkeitsnachweis für diese Sprache hinter meinem Link. Ohne Einschränkung der Allgemeinheit gehen wir davon aus, dass alle Zähler den gleichen Wert für die Selbstzurücksetzung haben (dh $f(x,x)$ ist für alle $x$ ). Dies ist eine sichere Annahme, da das Hinzufügen derselben Konstante zu jedem f ( x , y ) für ein bestimmtes $x$ das Verhalten des Programms nicht ändert.$f(x,y)$

Sei $p$ die Anzahl der Zähler; ohne Beschränkung der Allgemeinheit (Artin Vermutung vorausgesetzt) sei angenommen , dass $p$ a hat Primitivwurzel 2. Es sei $q$ sein , $p(1+s+s^2)$ , wobei $s$ die niedrigste Potenz von 2 größer ist , $p$ . Ohne Verlust der Allgemeinheit wird $2q$ kleiner als $2^p$ ( $2q$ ist polynomiell begrenzt, $2^p$ wächst exponentiell, so dass jedes ausreichend große $p$ funktioniert).

Die Bandanordnung ist wie folgt: Wir nummerieren jeden Zähler mit einer ganzen Zahl $0 \leq i < p$ (und ohne Verlust der Allgemeinheit nehmen wir an, dass es einen einzelnen Stoppzähler gibt und nummerieren ihn mit $2$ ). Der Wert der meisten Zähler wird auf Band Zelle gespeichert $2^i$ , mit Ausnahme des Zählers 0 ist , die sich auf Bandzelle gespeichert ist $2q$ . Für jede ungeradzahlige Bandzelle von Zelle -1 bis einschließlich $2^{p+1}+2p+1$Diese Bandzelle enthält immer 1, es sei denn, sie befindet sich unmittelbar links von einem Zähler. In diesem Fall enthält sie immer 0. Bandzellen mit gerader Nummer, die nicht als Zähler verwendet werden, haben irrelevante Werte (die 0 sein können oder nicht) ); und ungeradzahlige Bandzellen außerhalb des angegebenen Bereichs haben ebenfalls irrelevante Werte. Es ist zu beachten, dass zum Einstellen des Bandes in einen geeigneten Anfangszustand nur eine begrenzte Anzahl von Bandelementen auf konstante Werte initialisiert werden muss. Dies bedeutet, dass wir dies mit einer Abfolge von <>+-Anweisungen tun können (in der Tat werden nur Anweisungen >+benötigt), also keine Klammern. Am Ende dieser Initialisierung verschieben wir den Bandzeiger auf Zelle -1.

Die allgemeine Form unseres Programms sieht folgendermaßen aus:

Initialisierung [>>>[ >$\times(2^p-1)$ [ <$\times(2p)$ ]>-] Einstellung <<<]

Die Initialisierung bringt das Band in die erwartete Form und den Zeiger auf Zelle -1. Dies ist nicht die Zelle links von einem Zähler (0 ist keine Potenz von 2), also hat sie den Wert 1, und wir betreten die Schleife. Die Schleifeninvariante für diese äußerste Schleife besteht darin, dass sich der Bandzeiger (am Anfang und Ende jeder Schleifeniteration) drei Zellen links von einem Zähler befindet. Es ist zu sehen, dass die Schleife nur dann beendet wird, wenn wir drei Zellen links von Zähler 2 sind (jeder andere Zähler hat eine 1, drei Zellen links davon, da eine 0 die Bandposition von zwei Zählern bedeuten würde waren 2 Zellen auseinander, die einzigen zwei Potenzen von 2, die sich durch 2 unterscheiden, sind $2^1$ und $2^2$ , und die binäre Darstellung von $q$ ändert sich von Zeichenfolgen von $0$ s zu Zeichenfolgen von$1$ s oder umgekehrt mindestens viermal und kann daher nicht 1 von einer Potenz von 2) entfernt sein.

Die zweite Schleife durchläuft die Zähler wiederholt und dekrementiert sie. Die Schleifeninvariante ist, dass der Bandzeiger immer auf einen Zähler zeigt. somit wird die Schleife beendet, wenn irgendein Zähler 0 wird. Die Dekrementierung ist gerade -; Die Art und Weise, wie wir von einer Theke zur nächsten gelangen, ist komplexer. Die Grundidee ist, dass das Verschieben von $2^p-1$ Feldern nach rechts von $2^x$ uns auf eine ungeradzahlige Zelle $2^p+2^x-1$ , die sich rechts von jedem Zähler befindet ( $2^p$ ist der letzte Zähler, $2^x-1$ ist positiv, weil $x$$2p$$2^x+1$$2p$$2p$$2^x+1$$2p$$2q-1$$-1$$2p$$2^{\log_{2,p}(r)+1}-1$ is congruent to $2r-1$ for any other $r$, where $\log_{2,p}$ is the discrete logarithm to base 2 modulo $p$). Additionally, it can be seen that the position of the tape pointer modulo $2p$ increases by $2$ each time round the middle loop. Thus, the tape pointer must cycle between all $p$ counters (in order of their values modulo $2p$). Thus, every $p$ iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).

When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of $f$; for every pair $(x,y)$, it adds $f(x,y)$ to the tape element which is the same distance left/right of the current tape pointer as counter $y$'s tape location is left/right of counter $x$'s tape location (and then removes the tape pointer back to where it started). Whenever $x\neq y$, this distance turns out to be unique:

• The difference between two powers of 2 is a binary number consisting of a string of 1 or more $1$s followed by a string of 0 or more $0$s (with the place values of the start of the number, and the start of the $0$ string, depending on the larger and smaller respectively of $x$ and $y$); thus all those differences are distinct. * As for the difference of a power of 2 and $q$, it must contain at least two transitions between strings of $1$s and $0$s ($q$ contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.

For $x=y$, we obviously find that the distance moved is 0. But because all $f(x,y)$ are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.

Thus, we now have a working compilation of any program in The Waterfall Model to BF (including halt behaviour, but not including I/O, which isn't needed for Turing-completeness) using only three pairs of brackets, and thus three pairs of brackets are enough for Turing-completeness.