Próbowałem znaleźć wyjaśnienia w Google, ale większość linków mówi tylko: „FRACTRAN jest w pełni gotowy. Na przykład spójrzmy na mnożenie”.
Pamiętam, jak zobaczyłem wpis na forum xkcd, że FRACTRAN pomógł plakatowi zrozumieć kompletność Turinga. Szukam intuicyjnego wyjaśnienia, dlaczego ten esolang jest ukończony przez Turinga, ponieważ nie jest to bardzo oczywiste, patrząc na mechanikę języka.
turing-completeness
komar
źródło
źródło
Odpowiedzi:
Aby imperatywny język był kompletny w Turinga, musi mieć:
FRACTRAN to język składający się z szeregu ułamków, które przechowują jego dane w wykładnikach liczb pierwszych.
Powiedzmy, że chcesz dodać dwie liczby: 2 a 3 b staje się 5 ab
To jest program FRACTRAN do robienia powyższej zmiany.
Zaczynasz od liczby 72 (2 3 3 2 ). Program przesuwa się do przodu, aż znajdzie liczbę, która pomnożona przez instrukcję jest kolejną liczbą całkowitą (niedozwolone są pozostałe).
72
będzie biegać do przodu, aż dojdzie do11/2
. Następnie podzieli liczbę2
i pomnoży ją11
(moc w 11 jest zmienną). To daje396
.396
dzieli się przez 33 (zmniejszając moc 3 i 11) i mnożąc przez 455 (zwiększając zmienne 5, 7 i 13). I tak dalej. Pełny opis tego programu i jego tabelę stanów można przeczytać na stronie wikipedii FRACTRAN , w tym naprawdę fajny animowany gif powyższego programu.Inne materiały FRACTRAN na temat wymiany stosów, które dotyczą kompletności Turinga, można znaleźć na stronie: Przekształć Fractran w Brainfuck (ok, to naprawdę produktywne wykorzystanie własnego czasu)
Część trick tutaj (i to rozpoczęcie błądzą w teorii) jest to, że za kulisami, jest to maszyna rejestru Minsky , dla których został on udowodnił, że niektóre Taśmy (programy) są maszyny Turinga IF taśma jest reprezentowany jako liczba Gödla , która jest dokładnie jaki jest numer FRACTRAN (z powiązanej strony wikipedii):
Mamy więc pętle warunkowe, dowolne zmienne przechowywane jako liczby Gödla, mamy maszynę Turinga.
Inne zabawy, które dotykają Collatz, takie jak natura FRACTRAN, można przeczytać w Can't Decide? Niezdecydować! które wiążą hipotezę Collatza z FRACTRAN i problemem zatrzymania.
FRACTRAN jest trochę trudny do opanowania.
Rozważ ten program jak:
W tym przypadku każdy blok ma postać:
Pierwsza instrukcja z powyższego programu do mnożenia:
Zostanie napisany w tej formie jako:
W ten sposób wyraźnie widać pamięć danych i konstrukcje zapętlania niezbędne dla kompletności Turinga. Jest bardzo szczątkowy, ale istnieje i działa jak prosta maszyna rejestrująca - ale to wszystko, co naprawdę musisz zrobić.
Nadal nie jesteś przekonany?
To w dużej mierze zapożycza z wykładu Dimitri Hendricksa na temat modeli obliczeniowych
Wymaga to bardzo prostego programu,
(2/3)
który jest sumatorem (2 a 3 b -> 3 a + b ) Ale jest destrukcyjny - wartość w 2 jest usuwana jako część procesu.Napiszmy FRACTRAN wyższego poziomu, który ułatwia takie zniszczenie.
Oryginalny program można uznać za:
W F 2 można określić swego rodzaju „funkcje”.
Aby przekonwertować program F 2 (P) na standardowy program FRACTRAN, należy:
staje się:
To, co zostało zrobione, jest używane przez liczby pierwsze p, q, r i s do przechowywania stanu programu.
A potem mamy maszynę rejestrów ... ma skończoną liczbę rejestrów, które przechowują dowolne duże liczby i dwie instrukcje:
Wykazano, że ten rejestrator jest ukończony.
Następnie pokazuje proces na kilku slajdach kompilowania programu maszyny rejestrowej do programu FRACTRAN jako część procesu mechanicznego.
Gruntownie:
A zatem ze względu na równoważność między tymi dwoma modelami przetwarzania danych, FRACTRAN jest w Turingu kompletny.
A tak przy okazji, jeśli naprawdę chcesz, aby twój umysł był zdumiony, przeczytaj Code Golf: Fractran, w którym niektórzy napisali program FRACTRAN, aby uruchomić inny program FRACTRAN.
źródło