Brainfuck to kompletny język programowania Turinga, który używa tylko 8 symboli (6, jeśli zignorujesz I / O).

Dwa najbardziej godne uwagi te, które popychają go do Kompletność Turinga są [i ]zasadniczo etykieta i goto brainfuck użytkownika.

Zwykle programy w Brainfuck używają wielu zestawów [], ale zastanawiałem się dokładnie, ile par tych nawiasów trzeba użyć, aby Brainfuck Turing był kompletny?

Mówiąc prościej, jaka jest najmniejsza liczba nawiasów potrzebna do symulacji n-stanowej maszyny Turinga (Podaj liczbę nawiasów dla 1, 2 i trzech stanów maszyn Turinga)?

Uwagi:

Zakładamy nieskończoną taśmę i brak ograniczeń obliczeniowych.

Jest to 2-symbolowa maszyna Turinga

Jest to dalszy rozwój odpowiedzi @ ais523 , zmniejszając ją do tylko dwóch zestawów nawiasów, a także stosując bardziej zwarte umieszczanie komórek oparte na teorii linijki Golomba. ais523 stworzył kompilator dla tej konstrukcji , a także dla tej sesji TIO pokazującej przykładowy wynikowy program BF działający ze śledzeniem debugowania liczników TWM.

Podobnie jak oryginał, zaczyna się od programu w The Waterfall Model , z pewnymi ograniczeniami, które nie tracą ogólności:

1. Wszystkie liczniki mają tę samą wartość samoresetującą $R$ ; to znaczy mapa wyzwalacza TWM $f$ ma właściwość, że $f(x,x)=R$ dla wszystkich $x$ .
2. Jest jeden licznik zatrzymania $h$ .
3. Liczba $c$ liczników wynosi $(p-1)/2$ dla niektórych liczb pierwszych $p$ .

Władca Golombów

Łączymy konstrukcję Erdős – Turán z funkcją permutacji tablicy Welch – Costas , aby uzyskać linijkę Golomb o niezbędnych właściwościach.

(Jestem pewien, że ta połączona konstrukcja nie może być nowym pomysłem, ale właśnie znaleźliśmy i dopasowaliśmy te dwa elementy z Wikipedii.)

Niech $r$ będzie pierwotnym pierwiastkiem z $p=2c+1$ . Zdefiniuj funkcję

1. $g$ jestlinijką Golombarzędu$2c$ . Oznacza to, że różnica$g(i)-g(j)$ jest unikalna dla każdej pary odrębnych liczb$i,j \in \{0,\ldots,2c-1\}$ .
2. $g(k)\bmod(2c)$ przyjmuje każdą wartość$0,\ldots,2c-1$ dokładnie raz.

Struktura taśmy

Dla każdego licznika TWM $x\in \{0,\ldots,c-1\}$ przypisujemy dwie pozycje komórki taśmy BF, komórkę rezerwową $u(x)$ i komórkę wartości $v(x)$ :

Drugą właściwością $g$ są dokładnie dwie różne wartości $k_1,k_2$ do wyboru.

Zawartość komórki rezerwowej będzie przez większość czasu utrzymywana na poziomie $0$ , z wyjątkiem sytuacji, gdy jej licznik został właśnie odwiedzony, gdy będzie miał wartość $2R$ , czyli dwukrotnie wartość samoresetu licznika. Komórka wartości będzie utrzymywana na poziomie dwukrotności wartości odpowiedniego licznika TWM.

Wszystkie pozostałe komórki, do których może dojść podczas wykonywania programu BF (liczba skończona), będą miały nieparzyste wartości, dzięki czemu zawsze będą testowane jako niezerowe. Po inicjalizacji jest to automatyczne, ponieważ wszystkie korekty komórek są dokonywane w równych ilościach.

W razie potrzeby wszystkie pozycje komórek można przesunąć w prawo o stałą, aby uniknąć przesunięcia się na lewo od początkowej pozycji taśmy BF.

Struktura programu BF

Niech $H = v(h)-u(h)$ będzie odległością między wartością licznika zatrzymania a komórkami zastępczymi, i niech $N$ będzie liczbą wystarczająco dużą, aby $cN+1 \geq v((x+1)\bmod c) - u(x)$ dla wszystkich liczników $x$ . Zatem podstawowa struktura programu BF to

inicjalizacja [ >$\times (H+cN+1)$ [ <$\times c$ ] korekty <$\times H$ ]

Inicjalizacja

Faza inicjalizacji ustawia wszystkie komórki osiągalne przez program do ich wartości początkowych, w stanie, jakby ostatni licznik został właśnie odwiedzony, a właśnie aktywna komórka była komórką zastępczą $u(c-1)$ :

1. Komórki wartości są inicjowane do dwukrotności początkowej zawartości odpowiedniego licznika TWM, z tym wyjątkiem, że licznik $0$ jest wstępnie zmniejszany.
2. Komórki awaryjnej wartość $0$ , z wyjątkiem komórek $u(c-1)$ , który jest ustawiony na $2R$ .
3. Wszystkie pozostałe komórki osiągalne przez program (liczba skończona) są ustawione na $1$ .

Następnie wskaźnik taśmy przesuwa się do pozycji $u(c-1)-H$ (zawsze niezerowa komórka), zanim dotrzemy do pierwszego programu [.

Początek zewnętrznej pętli

Na początku iteracji zewnętrznej pętli wskaźnik taśmy będzie miał wartość $u(x)-H$ lub $v(x)-H$ dla licznika $x$ .

Niech $y=((x+1)\bmod c)$ będzie następnym licznikiem do odwiedzenia.

Ruch >$\times (H+cN+1)$ umieszcza wskaźnik taśmy na pozycji $\equiv y\pmod c$ a nie po lewej stronie$v(y)$ .

Wewnętrzna pętla [ <$\times c$ ] szuka teraz w lewo w krokach $c$ dla komórki zerowej. Jeśli licznik $y$ wynosi zero, to zatrzyma się na komórce wartości (zero) $v(y)$ ; w przeciwnym razie znajdzie komórkę rezerwową $u(y)$ .

Każda znaleziona komórka staje się nową aktywną komórką.

Korekty

Regulacji fazy reguluje różne komórki na taśmie w oparciu o ich położenia w stosunku do komórki aktywnej. Ta sekcja zawiera tylko +-><polecenia, więc te korekty odbywają się bezwarunkowo. Ponieważ jednak wszystkie powiązane z sobą komórki są wzorami linijki Golomba, wszelkie korekty, które nie są właściwe dla bieżącej aktywnej komórki, pominą wszystkie ważne komórki i dostosują niektóre nieistotne komórki (zachowując to nieparzyste).

Oddzielny kod musi zatem zostać zawarty w programie dla każdej możliwej wymaganej pary aktywnej i skorygowanej komórki, z wyjątkiem samoregulacji aktywnej komórki, która ponieważ dostosowanie opiera się wyłącznie na pozycji względnej, musi być dzielona między nimi wszystkimi.

Wymagane korekty to:

1. Dostosować poprzedni stan licznika komórek zastępczej $u(x)$ przez $-2R$ .
2. Dostosuj komórkę cofania $u(y)$ licznika prądu o $2R$ , z wyjątkiem sytuacji, gdy bieżącą komórką aktywną jest $v(h)$ i dlatego powinniśmy się zatrzymać.
3. Dostosuj komórkę wartości następnego licznika $v((y+1)\bmod c)$ o $-2$ (zmniejszając licznik).
4. Gdy aktywna komórka jest komórką wartości $v(y)$ (więc licznik $y$ osiągnął zero), dostosuj wszystkie komórki wartości $v(z)$ o $2f(y,z)$ z mapy wyzwalacza TWM. $v(y)$ sam zostaje skorygowane przez $2R$ .

Pierwsza i druga korekta powyżej są konieczne ze względu na fakt, że wszystkie aktywne komórki muszą dostosować się o tę samą wartość, która wynosi $2R$ dla komórek wartości, a zatem także dla komórek rezerwowych. Wymaga to przygotowania i wyczyszczenia komórek rezerwowych, aby upewnić się, że wrócą do $0$ zarówno w gałęzi wartości, jak i rezerwowych.

Koniec zewnętrznej pętli

Ruch <$\times H$ oznacza, że ​​pod koniec fazy dostosowywania wskaźnik taśmy przesuwa się $H$ na lewo od aktywnej komórki.

Dla wszystkich aktywnych komórek innych niż komórka wartości licznika zatrzymania $v(h)$ jest to komórka nieistotna, a więc nieparzysta i niezerowa, a zewnętrzna pętla kontynuuje kolejną iterację.

W przypadku $v(h)$ wskaźnik jest zamiast tego umieszczany na odpowiadającej mu komórce rezerwowej $u(h)$ , dla której zrobiliśmy wyjątek powyżej, aby utrzymać go na zero, a więc program wychodzi przez finał ]i zatrzymuje się.

Nie jestem w 100% pewien, że nie da się tego zrobić za pomocą dwóch zestawów nawiasów. Jeśli jednak komórki taśmy BF dopuszczają nieograniczone wartości, wystarczą trzy zestawy nawiasów. (Dla uproszczenia założę również, że możemy przesunąć głowicę taśmy w lewo poza jej punkt początkowy, chociaż ponieważ ta konstrukcja wykorzystuje tylko skończony obszar taśmy, możemy znieść to ograniczenie, dodając wystarczająco wiele >poleceń na początku program.) Poniższa konstrukcja wymaga przypuszczenia Artinaaby móc kompilować dowolnie duże programy; jednak nawet jeśli hipoteza Artina jest fałszywa, nadal będzie można pośrednio wykazać kompletność Turinga poprzez przetłumaczenie tłumacza języka kompletnego Turinga na BF przy użyciu poniższej konstrukcji i uruchomienie dowolnych programów poprzez przekazanie ich jako danych wejściowych do tego tłumacza.

Kompletnym językiem Turinga, który kompilujemy w nieograniczony BF, jest The Waterfall Model , który jest jednym z najprostszych znanych modeli obliczeniowych. Dla osób, które jeszcze tego nie wiedzą, składa się z kilku liczników (i ich wartości początkowych) oraz funkcji $f$ od par liczników do liczb całkowitych; wykonanie programu polega na wielokrotnym odejmowaniu 1 od każdego licznika, a następnie jeśli dowolny licznik $x$ wynosi 0, dodawanie $f(x,y)$ do każdego licznika $y$(program jest napisany w taki sposób, że nigdy nie dzieje się to z wieloma licznikami jednocześnie). Za moim linkiem jest dowód kompletności Turinga dla tego języka. Bez utraty ogólności założymy, że wszystkie liczniki mają tę samą wartość samoresetu (tj. $f(x,x)$ jest takie samo dla wszystkich $x$ ); jest to bezpieczne założenie, ponieważ dla każdego konkretnego $x$ dodanie tej samej stałej do każdego $f(x,y)$ nie zmieni zachowania programu.

Niech $p$ będzie liczbą liczników; bez utraty ogólności (zakładając przypuszczenie Artina), załóżmy, że $p$ ma pierwotny pierwiastek 2. Niech$q$ będzie$p(1+s+s^2)$ , gdzie$s$ jest najniższą potęgą 2 większą niż$p$ . Bez utraty ogólności,$2q$ będzie mniejsze niż$2^p$ ($2q$ jest ograniczone wielomianem,$2^p$ rośnie wykładniczo, więc każde wystarczająco duże$p$ będzie działać).

Układ taśm jest następujący: każdy licznik numerujemy liczbą całkowitą $0 \leq i < p$ (i bez utraty ogólności zakładamy, że istnieje jeden licznik zatrzymania i numerujemy go $2$ ). Wartość większości liczników jest przechowywana na komórce taśmy $2^i$ , z wyjątkiem licznika 0, który jest przechowywany na komórce taśmy $2q$ . Dla każdej nieparzystej komórki taśmy od komórki -1 do 2 p + 1 + 2 p + 1 włącznie$2^{p+1}+2p+1$, ta komórka taśmy zawsze ma wartość 1, chyba że znajduje się bezpośrednio na lewo od licznika, w którym to przypadku zawsze ma wartość 0. Parzyste komórki taśmy, które nie są używane jako liczniki, mają nieistotne wartości (które mogą, ale nie muszą mieć wartości 0 ); i nieparzyste komórki taśmowe poza podanym zakresem mają również nieistotne wartości. Zauważ, że ustawienie taśmy w odpowiedni stan początkowy wymaga zainicjowania tylko skończonej liczby elementów taśmy do stałych wartości, co oznacza, że ​​możemy to zrobić za pomocą sekwencji <>+-instrukcji (w rzeczywistości >+potrzebne są tylko ), a zatem nie ma nawiasów. Pod koniec tej inicjalizacji przenosimy wskaźnik taśmy do komórki -1.

Ogólny kształt naszego programu będzie wyglądał następująco:

inicjalizacja [>>>[ >$\times(2^p-1)$ regulacja ( 2 p - 1 ) [ <$\times(2p)$ ]>-] <<<]

Inicjalizacja umieszcza taśmę w oczekiwanym kształcie, a wskaźnik na komórce -1. To nie jest komórka po lewej stronie licznika (0 nie jest potęgą 2), więc ma wartość 1 i wchodzimy do pętli. Niezmiennikiem pętli dla tej najbardziej zewnętrznej pętli jest to, że wskaźnikiem taśmy jest (na początku i na końcu każdej iteracji pętli) trzy komórki na lewo od licznika; można zauważyć, że pętla zakończy się w ten sposób tylko wtedy, gdy będziemy trzy komórki po lewej stronie licznika 2 (każdy inny licznik ma 1 trzy komórki po lewej stronie, ponieważ w przypadku liczby 0 oznaczałoby to, że pozycje taśmy dwóch liczników były 2 komórki od siebie; jedyne dwie potęgi 2, które różnią się o 2, to $2^1$ i $2^2$ , a reprezentacja binarna $q$ zmienia się z ciągów $0$ s na ciągi$1$ s lub odwrotnie co najmniej cztery razy, a zatem nie może być 1 od potęgi 2).

Druga pętla wielokrotnie zapętla się nad licznikami, zmniejszając je. Niezmiennikiem pętli jest to, że wskaźnik taśmy zawsze wskazuje na licznik; zatem pętla zakończy się, gdy jakiś licznik osiągnie wartość 0. Zmniejszenie jest po prostu dodatnie); modulo 2 p , ta wartość jest zgodna z (według Małego Twierdzenia Fermata) 2 x p , a 2 log 2 , p ( r ) + 1 - 1 jest zgodna z 2 r- ; sposób, w jaki przechodzimy od jednego licznika do drugiego, jest bardziej złożony. Podstawową ideą jest to, że przesunięcie $2^p-1$ spacji w prawo od $2^x$ spowoduje umieszczenie nas na nieparzystej komórce $2^p+2^x-1$ , która znajduje się po prawej stronie dowolnego licznika ( $2^p$ jest ostatnim licznikiem, $2^x-1$ jest dodatnia, ponieważ $x$$2p$$2^x+1$ . Wewnętrzna pętla wielokrotnie przesuwa się w lewo oodstępy$2p$ , nie zmieniając również wskaźnika komórki taśmy modulo$2p$ , i ostatecznie musi znaleźć komórkę przystającą do$2^x+1$ modulo$2p$ która ma wartość (która będzie komórką do na lewo od licznika); z powodu naszych prymitywnych wymagań dotyczących korzeni istnieje dokładnie jedna taka komórka ($2q-1$ przystaje do$-1$ modulo$2p$$2^{\log_{2,p}(r)+1}-1$$2r-1$ dla każdego innego$r$ , gdzie$\log_{2,p}$ jest dyskretnym logarytmem dla podstawy 2 modulo$p$ ). Ponadto, można zauważyć, że położenie wskaźnika taśmy modulo$2p$ wzrasta o$2$ za każdym razem okrągłą środkowego pętli. Zatem wskaźnik taśmy musi przełączać się między wszystkimilicznikami$p$ (w kolejności ich wartości modulo$2p$ ). Tak więc każdy$p$ iteracjach zmniejszamy każdy licznik (zgodnie z wymaganiami). Jeśli pętla ulegnie częściowemu pęknięciu podczas iteracji, wznowimy zmniejszanie po ponownym wejściu do pętli (ponieważ reszta najbardziej zewnętrznej pętli nie powoduje zmiany siatki w pozycji wskaźnika taśmy).

Kiedy licznik osiągnie 0, środkowa pętla pęka, przenosząc nas do kodu „regulacji”. Jest to w zasadzie tylko kodowanie$f$$(x,y)$$f(x,y)$$y$$x$$x\neq y$

• Różnica między dwiema potęgami 2 to liczba binarna składająca się z ciągu 1 lub więcej $1$$0$$0$$x$$y$$q$$1$$0$$q$ zawiera co najmniej cztery takie przejścia, odejmowanie może usunąć tylko 2), a zatem różni się od wszystkich różnic dwóch potęg dwóch, a różnice te oczywiście również różnią się od siebie.

$x=y$$f(x,y)$

Tak więc mamy teraz działającą kompilację dowolnego programu w The Waterfall Model do BF (w tym zachowanie zatrzymania, ale bez uwzględnienia I / O, które nie jest potrzebne do kompletności Turinga) przy użyciu tylko trzech par nawiasów, a zatem trzech par nawiasów wystarczy do kompletności Turinga.