Dlaczego FRACTRAN Turing jest gotowy?

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.

Aby imperatywny język był kompletny w Turinga, musi mieć:

1. Pętla warunkowa
2. Dowolna liczba zmiennych

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

455 11 1 3 11 1
---, -, -, -, -, -
 33 13 11 7 2 3

To jest program FRACTRAN do robienia powyższej zmiany.

Zaczynasz od liczby 72 (2 ³ 3 ² ). Program przesuwa się do przodu, aż znajdzie liczbę, która pomnożona przez instrukcję jest kolejną liczbą całkowitą (niedozwolone są pozostałe).

72będzie biegać do przodu, aż dojdzie do 11/2. Następnie podzieli liczbę 2i pomnoży ją 11(moc w 11 jest zmienną). To daje 396. 396dzieli 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)

Powodem, dla którego Fractran jest Turing-complete, jest to, że symuluje maszynę rejestrującą. Rozkład na czynniki pierwsze liczby przechowuje zawartość rejestrów, podczas gdy dzielenie i mnożenie jest sposobem warunkowego dodawania i odejmowania od rejestrów.

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

Gödel zastosował system oparty na rozkładzie na czynniki pierwsze. Najpierw przypisał unikalny numer naturalny do każdego podstawowego symbolu w formalnym języku arytmetyki, z którym miał do czynienia.

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:

LABEL: start
    block1
    block2
    block3
    ...
END

W tym przypadku każdy blok ma postać:

IF(registers X >= a, Y >= b)  # or any combination of registers
THEN
    X -= a
    Y -= b

    I += n
    J += m

    goto start

Pierwsza instrukcja z powyższego programu do mnożenia:

455
---
 33

Zostanie napisany w tej formie jako:

IF(register `3` >= 1 && `11` >= 1)
THEN
     `3` -= 1
    `11` -= 1

     `5` += 1
     `7` += 1
    `13` += 1

    goto start

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:

   2)
α: - → α
   3)

W F ₂ można określić swego rodzaju „funkcje”.

   10 1
α: - → α, - → β
    3 1

   3)
β: - → β
   5 

Aby przekonwertować program F ₂ (P) na standardowy program FRACTRAN, należy:

1. Wyczyść P pętli o długości 1
2. Zastąp litery greckie (funkcje) świeżymi liczbami pierwszymi
3. Zastąp przejścia:

   as
p: - → q, - → r, - -> s, ...
   bdf

staje się:

aq cr es
-, -, -, ...
bp dp fp

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:

• inc (x _i , m) - rejestr przyrostowy i idź do linii m
• jzdec (x _i , m ₁ , m ₂ ) - jeśli rejestr i wynosi 0, przejdź do linii m, w innym przypadku zmniejsz i i przejdź do linii m2.

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:

                       Liczba Pi)
inc (x (i), m) = ---- → m
                        1

                        1 1
jzdec (x (i), m1, m2) = ---- → m2, - → m1
                       p (i) 1

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.