FRACTRAN

FRACTRAN – ezoteryczny język programowania wynaleziony przez matematyka Johna Conwaya[1][2], będący zupełny w sensie Turinga[3].

Program w języku FRACTRAN ma postać ciągu dodatnich ułamków nieskracalnych. Wejściem dla programu jest dodatnia liczba całkowita n. Wykonanie programu polega na wielokrotnym zmienianiu wartości n przez następującą operację: „znajdź pierwszy w ciągu ułamek f, dla którego iloczyn nf jest liczbą całkowitą, i zastąp n przez nf”. Jeśli żaden ułamek w ciągu nie daje liczby całkowitej po pomnożeniu przez obecną wartość n, wykonywanie programu zostaje zatrzymane[1].

Nazwa stanowi połączenie słowa „fraction” (ułamek) oraz nazwy języka programowania FORTRAN[3].

Przykładowym programem w języku FRACTRAN jest PRIMEGAME[a] autorstwa Conwaya[1], który po uruchomieniu znajduje kolejne liczby pierwsze:

( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 2 , 1 7 , 55 1 ) . {\displaystyle \left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}\right).}

Jeśli na wejściu zostanie podana liczba n = 2 , {\displaystyle n=2,} program ten generuje następujący ciąg liczb:

  • 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, ... (ciąg publikacja w otwartym dostępie – możesz ją przeczytać A007542 w OEIS)

Nie licząc początkowej dwójki, ciąg ten zawiera następujące potęgi 2: 4 = 2 2 , 8 = 2 3 , 32 = 2 5 , 128 = 2 7 , 2048 = 2 11 , 8192 = 2 13 , 131072 = 2 17 , 524288 = 2 19 , … {\displaystyle 4=2^{2},\,8=2^{3},\,32=2^{5},\,128=2^{7},\,2048=2^{11},\,8192=2^{13},\,131072=2^{17},\,524288=2^{19},\,\dots } (ciąg publikacja w otwartym dostępie – możesz ją przeczytać A034785 w OEIS). Wykładniki tych potęg są kolejnymi liczbami pierwszymi.

Zasada działania programu FRACTRAN

Program FRACTRAN można rozumieć jako rodzaj maszyny rejestrowej, gdzie zawartość rejestrów jest przechowywana w wykładnikach potęg czynników pierwszych w rozkładzie argumentu n[2]. Na przykład wartość n równa 60 = 2 2 × 3 1 × 5 1 {\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}} reprezentuje stan rejestrów, w którym jedna zmienna (nazwana v2) ma wartość 2, a dwie inne zmienne (v3 i v5) mają wartość 1. Wszystkie inne zmienne mają wartość 0.

Program FRACTRAN ma postać uporządkowanej listy dodatnich ułamków nieskracalnych. Każdy ułamek reprezentuje instrukcję, która przeprowadza operacje na zawartości jednej lub więcej zmiennych, określonych przez czynniki pierwsze mianownika danego ułamka. Na przykład instrukcja

f 1 = 21 20 = 3 1 × 7 1 2 2 × 5 1 {\displaystyle f_{1}={\frac {21}{20}}={\frac {3^{1}\times 7^{1}}{2^{2}\times 5^{1}}}}

sprawdza zawartość v2 i v5. Jeśli v 2 ⩾ 2 {\displaystyle v_{2}\geqslant 2} i v 5 ⩾ 1 , {\displaystyle v_{5}\geqslant 1,} instrukcja f 1 {\displaystyle f_{1}} odejmie 2 od v2 i 1 od v5 oraz doda 1 do v3 i 1 do v7. Na przykład:

60 ⋅ f 1 = 2 2 × 3 1 × 5 1 ⋅ 3 1 × 7 1 2 2 × 5 1 = 3 2 × 7 1 . {\displaystyle 60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3^{1}\times 7^{1}}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}.}

Tego rodzaju instrukcje „sprawdź-odejmij-dodaj” są w języku FRACTRAN jedynymi dozwolonymi instrukcjami[2].

Przykładowe programy FRACTRAN

Dodawanie

Najprostszy program FRACTRAN składa się z pojedynczej instrukcji, na przykład[1]

( 3 2 ) . {\displaystyle \left({\frac {3}{2}}\right).}

Program ten oblicza sumę dwóch liczb całkowitych, a {\displaystyle a} i b . {\displaystyle b.} Dla początkowej wartości n = 2 a 3 b {\displaystyle n=2^{a}3^{b}} program generuje sekwencję 2 a − 1 3 b + 1 , {\displaystyle 2^{a-1}3^{b+1},} 2 a − 2 3 b + 2 {\displaystyle 2^{a-2}3^{b+2}} itd., aż w końcu, po a {\displaystyle a} krokach, program zatrzyma się z końcowym wynikiem 3 a + b . {\displaystyle 3^{a+b}.}

Nieco bardziej skomplikowany wariant programu dodającego składa się z dwóch instrukcji[2]:

( 10 3 , 3 5 ) . {\displaystyle \left({\frac {10}{3}},{\frac {3}{5}}\right).}

Dla wejściowej wartości n = 2 a 3 b {\displaystyle n=2^{a}3^{b}} program zatrzyma się z wynikiem 2 a + b 3 b . {\displaystyle 2^{a+b}3^{b}.} Dzięki temu informacja o wartościach a {\displaystyle a} i b {\displaystyle b} nie zostaje zniszczona.

W tym wariancie zmienna v5 tymczasowo przechowuje początkową wartość v3 = b . {\displaystyle b.} Pierwsza instrukcja 10 3 = 2 ⋅ 5 3 {\displaystyle {\frac {10}{3}}={\frac {2\cdot 5}{3}}} przenosi zawartość v3 do v2 oraz v5; gdy v3 osiągnie wartość zero, program zaczyna wykonywać drugą instrukcję 3 5 , {\displaystyle {\frac {3}{5}},} która odtwarza wartość v3 z v5.

Mnożenie – przykład pętli

Następujący program[2] przyjmuje na wejściu liczbę n = 2 a ⋅ 3 b ⋅ 7 c ⋅ 11 {\displaystyle n=2^{a}\cdot 3^{b}\cdot 7^{c}\cdot 11} i zatrzymuje się z końcowym wynikiem n = 2 a + b c ⋅ 3 b ⋅ 11 , {\displaystyle n=2^{a+bc}\cdot 3^{b}\cdot 11,} tym samym obliczając wynik mnożenia b c : {\displaystyle bc{:}}

( 13 77 , 170 39 , 13 17 , 19 13 , 69 95 , 19 23 , 11 19 ) . {\displaystyle \left({\frac {13}{77}},{\frac {170}{39}},{\frac {13}{17}},{\frac {19}{13}},{\frac {69}{95}},{\frac {19}{23}},{\frac {11}{19}}\right).}

Działanie programu polega na wykonywaniu procedury dodającej w pętli, tak, by dodać b {\displaystyle b} do a {\displaystyle a} dokładnie c {\displaystyle c} razy.

Aby zaimplementować w języku FRACTRAN pętlę, należy wprowadzić pojęcie stanu. W tym celu należy wybrać pewne liczby pierwsze jako wskaźniki stanu: dla powyższego programu mnożącego są to 11, 13, 17, 19 i 23. Na przykład jeśli w danym kroku wartość n jest podzielna przez 11 i niepodzielna przez żadną inną z tych liczb, oznacza to, że program jest w stanie „11”.

By przeanalizować działanie programu, dla większej jasności można go zapisać w następujący sposób:

( 13 7 ⋅ 11 , 2 ⋅ 5 ⋅ 17 3 ⋅ 13 , 13 17 , 19 13 , 3 ⋅ 23 5 ⋅ 19 , 19 23 , 11 19 ) . {\displaystyle \left({\frac {13}{7\cdot 11}},{\frac {2\cdot 5\cdot 17}{3\cdot 13}},{\frac {13}{17}},{\frac {19}{13}},{\frac {3\cdot 23}{5\cdot 19}},{\frac {19}{23}},{\frac {11}{19}}\right).}

Działanie programu można opisać następująco[2]:

  • w chwili początkowej (wejściowa wartość n = 2 a ⋅ 3 b ⋅ 7 c ⋅ 11 {\displaystyle n=2^{a}\cdot 3^{b}\cdot 7^{c}\cdot 11} ) program jest w stanie 11. W pierwszym kroku – jeśli v7 > 0 – odejmuje 1 od v7 i przechodzi do stanu 13;
  • w kolejnych krokach program przechodzi na przemian między stanami 13 a 17 (pierwsza pętla). W każdym przebiegu tej pętli wykonuje pierwszą instrukcję algorytmu dodającego („odejmij 1 od v3 i dodaj 1 do v2, v5”);
  • gdy v3 osiągnie zero, pętla kończy się – ze stanu 13 program przechodzi do 19;
  • w kolejnych krokach program przechodzi na przemian między stanami 19 a 23 (druga pętla). W każdym przebiegu tej pętli wykonuje drugą instrukcję algorytmu dodającego („odejmij 1 od v5, dodaj 1 do v3”);
  • gdy v5 osiąga zero, druga pętla kończy się, a program przechodzi do początkowego stanu 11 i wykonywanie instrukcji zaczyna się od nowa.

Po każdym wykonaniu tego ciągu instrukcji zawartość v2 wzrasta o b , {\displaystyle b,} a zawartość v7 maleje o 1. Gdy v7 osiąga zero, program zatrzymuje się.

Algorytm generowania liczb pierwszych (PRIMEGAME)

Zaprezentowany na wstępie program PRIMEGAME, po wprowadzeniu na wejściu liczby n = 2 1 , {\displaystyle n=2^{1},} przeprowadza kolejno test pierwszości dla liczb N = 2 , 3 , 4 , 5... {\displaystyle N=2,3,4,5...} w następujący sposób. Program wykonuje pętlę, próbując podzielić liczbę N przez wszystkie możliwe dzielniki d = N − 1 , N − 2 , … 1. {\displaystyle d=N-1,N-2,\dots 1.} (Dzielenie zaimplementowane jest jako wielokrotne odejmowanie d od N, aż do uzyskania całkowitej części ilorazu oraz reszty z dzielenia.) Gdy program natrafi na największą wartość d, która dzieli N bez reszty, wyprowadza wartość n = 2 N 7 d − 1 {\displaystyle n=2^{N}7^{d-1}} i wykonuje algorytm od nowa dla kolejnej wartości N. Wartość 2 N 7 d − 1 {\displaystyle 2^{N}7^{d-1}} jest potęgą dwójki tylko wtedy, gdy d wynosi 1 – co ma miejsce tylko wtedy, gdy N jest liczbą pierwszą. Dokładniejsze wyjaśnienie krok po kroku algorytmu Conwaya można znaleźć u Guya (1983)[4] bądź Havila (2007)[2].

Dotarcie do liczby pierwszej 2, 3, 5, 7... zajmuje temu programowi odpowiednio 19, 69, 281, 710,... kroków od momentu uruchomienia (ciąg publikacja w otwartym dostępie – możesz ją przeczytać A007547 w OEIS).

Istnieje także wariant programu Conwaya[4][5], który różni się od powyższej wersji dwoma ułamkami:

( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 14 , 15 2 , 55 1 ) {\displaystyle \left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)}

Zasada działania tego wariantu jest taka sama, ale jest on nieco szybszy: by dotrzeć do kolejnych liczb pierwszych 2, 3, 5, 7..., potrzebuje on odpowiednio 19, 69, 280, 707... kroków (ciąg publikacja w otwartym dostępie – możesz ją przeczytać A007546 w OEIS). Pojedynczy przebieg programu, sprawdzający, czy liczba N jest pierwsza, wymaga następującej liczby kroków:

N − 1 + ( 6 N + 2 ) ( N − b ) + 2 ∑ d = b N − 1 ⌊ N d ⌋ , {\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,}

gdzie b < N {\displaystyle b<N} jest największym dzielnikiem całkowitym N, a ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } jest częścią całkowitą x[2][4].

W roku 1999 matematyk Devin Kilminster zademonstrował krótszy program znajdujący liczby pierwsze[2], składający się z dziesięciu instrukcji:

( 7 3 , 99 98 , 13 49 , 39 35 , 36 91 , 10 143 , 49 13 , 7 11 , 1 2 , 91 1 ) {\displaystyle \left({\frac {7}{3}},{\frac {99}{98}},{\frac {13}{49}},{\frac {39}{35}},{\frac {36}{91}},{\frac {10}{143}},{\frac {49}{13}},{\frac {7}{11}},{\frac {1}{2}},{\frac {91}{1}}\right)}

Dla początkowego wejścia n = 10 {\displaystyle n=10} kolejne liczby pierwsze są otrzymywane jako wykładniki potęg liczby 10.

Uwagi

  1. ↑ Nazwa pochodzi od angielskich słów: prime („liczba pierwsza”) i game („gra”).

Bibliografia

  1. ↑ a b c d John H. Conway: FRACTRAN: A simple universal programming language for arithmetic. W: Open Problems in Communication and Computation. New York: Springer-Verlag, 1987, s. 4–26. DOI: 10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6. [dostęp 2021-09-02]. (ang.).
  2. ↑ a b c d e f g h i Chapter 14: FRACTRAN. W: Julian Havil: Nonplussed!: Mathematical Proof of Implausible Ideas. Princeton, New Jersey: Princeton University Press, 2007, s. 162–179. ISBN 978-0-691-12056-0. [dostęp 2021-09-02]. (ang.).
  3. ↑ a b Siobhan Roberts: Genius at Play: The Curious Mind of John Horton Conway. New York: Bloomsbury, 2015, s. 115–119. ISBN 978-1-62040-593-2. [dostęp 2021-09-02]. (ang.).
  4. ↑ a b c Richard K. Guy. Conway’s Prime Producing Machine. „Mathematics Magazine”. 56 (1), s. 26–33, 1983. Taylor & Francis. DOI: 10.1080/0025570X.1983.11977011. [dostęp 2022-01-06]. (ang.). 
  5. ↑ John H. Conway, Richard K. Guy: The Book of Numbers. New York: Copernicus, 1996, s. 147. DOI: 10.1007/978-1-4612-4072-3. ISBN 978-1-4612-8488-8. (ang.).

Linki zewnętrzne

  • Eric W.E.W. Weisstein Eric W.E.W., FRACTRAN, [w:] MathWorld, Wolfram Research [dostęp 2021-07-16]  (ang.).
  • Fractran – hasło na wiki Esolang
  • Implementacja w języku Ruby i przykładowe programy. dev.gd. [zarchiwizowane z tego adresu (2013-01-25)]. – blog programisty Johna Biesneckera
  • Implementacja kompilatora do języka FRACTRAN w języku Lisp – blog programisty Michaela Malisa
  • Implementacja interpretera FRACTRAN w języku FRACTRAN. clomont.com. [zarchiwizowane z tego adresu (2018-01-04)]. – blog programisty Chrisa Lomonta