Tekst źródłowy strony FRACTRAN

'''FRACTRAN''' – [[ezoteryczny język programowania]] wynaleziony przez matematyka [[John Horton Conway|Johna Conwaya]]<ref name="Conway1987">{{cytuj książkę |tytuł = Open Problems in Communication and Computation |url = https://link.springer.com/chapter/10.1007%2F978-1-4612-4808-8_2 |wydawca = Springer-Verlag |miejsce = New York |rok = 1987 |strony = 4–26 |rozdział = FRACTRAN: A simple universal programming language for arithmetic |adres rozdziału = https://link.springer.com/chapter/10.1007%2F978-1-4612-4808-8_2 |nazwisko r = Conway |imię r = John H. |autor r link = John Horton Conway |isbn = 978-1-4612-9162-6 |doi = 10.1007/978-1-4612-4808-8_2 |język = en |data dostępu = 2021-09-02 |odn =}}</ref><ref name="Havil2007">{{cytuj książkę |nazwisko = Havil |imię = Julian |tytuł = Nonplussed!: Mathematical Proof of Implausible Ideas |url = https://archive.org/details/nonplussedmathem00havi |wydawca = Princeton University Press |miejsce = Princeton, New Jersey |rok = 2007 |isbn = 978-0-691-12056-0 |język = en |rozdział = Chapter 14: FRACTRAN |strony = 162–179 |data dostępu = 2021-09-02}}</ref>, będący [[Kompletność Turinga|zupełny w sensie Turinga]]<ref name="Roberts2015">{{cytuj książkę |nazwisko = Roberts |imię = Siobhan |tytuł = Genius at Play: The Curious Mind of John Horton Conway |url = https://archive.org/details/geniusatplaycuri0000robe |wydawca = Bloomsbury |miejsce = New York |rok = 2015 |isbn = 978-1-62040-593-2 |język = en |strony = 115–119 |data dostępu = 2021-09-02}}</ref>.

Program w języku FRACTRAN ma postać [[Ciąg (matematyka)|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<ref name="Conway1987" />.

Nazwa stanowi połączenie słowa „fraction” (ułamek) oraz nazwy języka programowania [[Fortran|FORTRAN]]<ref name="Roberts2015" />.

Przykładowym programem w języku FRACTRAN jest PRIMEGAME<ref group="uwaga">Nazwa pochodzi od angielskich słów: ''prime'' („liczba pierwsza”) i ''game'' („gra”).</ref> autorstwa Conwaya<ref name="Conway1987" />, który po uruchomieniu znajduje kolejne [[Liczba pierwsza|liczby pierwsze]]:
: <math>\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).</math>

Jeśli na wejściu zostanie podana liczba <math>n=2,</math> 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, ... {{OEIS|id=A007542}}

Nie licząc początkowej dwójki, ciąg ten zawiera następujące potęgi 2: <math>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</math>{{OEIS|id=A034785}}. Wykładniki tych potęg są kolejnymi liczbami pierwszymi.

== Zasada działania programu FRACTRAN ==
Program FRACTRAN można rozumieć jako rodzaj [[Maszyna rejestrowa|maszyny rejestrowej]], gdzie zawartość rejestrów jest przechowywana w wykładnikach potęg [[Czynnik pierwszy|czynników pierwszych]] w [[Rozkład na czynniki|rozkładzie]] argumentu ''n''<ref name="Havil2007" />. Na przykład wartość ''n'' równa <math>60 = 2^2 \times 3^1 \times 5^1</math> 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
: <math>f_1 = \frac{21}{20} = \frac{3^1 \times 7^1}{2^2 \times 5^1}</math>

sprawdza zawartość v2 i v5. Jeśli <math>v_2 \geqslant 2</math> i <math>v_5 \geqslant 1,</math> instrukcja <math>f_1</math> odejmie 2 od v2 i 1 od v5 oraz doda 1 do v3 i 1 do v7. Na przykład:
: <math>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.</math>

Tego rodzaju instrukcje „sprawdź-odejmij-dodaj” są w języku FRACTRAN jedynymi dozwolonymi instrukcjami<ref name="Havil2007" />.

== Przykładowe programy FRACTRAN ==
=== Dodawanie ===
Najprostszy program FRACTRAN składa się z pojedynczej instrukcji, na przykład<ref name="Conway1987" />
: <math>\left( \frac{3}{2} \right).</math>

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

Nieco bardziej skomplikowany wariant programu dodającego składa się z dwóch instrukcji<ref name="Havil2007" />:
: <math>\left( \frac{10}{3}, \frac{3}{5} \right).</math>

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

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

=== Mnożenie – przykład pętli ===
Następujący program<ref name="Havil2007" /> przyjmuje na wejściu liczbę <math>n = 2^a \cdot 3^b \cdot 7^c \cdot 11</math> i zatrzymuje się z końcowym wynikiem <math>n = 2^{a+bc} \cdot 3^b \cdot 11,</math> tym samym obliczając wynik mnożenia <math>bc{:}</math>
: <math>\left( \frac{13}{77}, \frac{170}{39}, \frac{13}{17}, \frac{19}{13}, \frac{69}{95}, \frac{19}{23}, \frac{11}{19} \right).</math>

Działanie programu polega na wykonywaniu procedury dodającej w [[Pętla (informatyka)|pętli]], tak, by dodać <math>b</math> do <math>a</math> dokładnie <math>c</math> razy.

Aby zaimplementować w języku FRACTRAN pętlę, należy wprowadzić pojęcie [[Stan obiektu (informatyka)|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:
: <math>\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).</math>

Działanie programu można opisać następująco<ref name="Havil2007" />:
* w chwili początkowej (wejściowa wartość <math>n = 2^a \cdot 3^b \cdot 7^c \cdot 11</math>) 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 <math>b,</math> 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 <math>n = 2^1,</math> przeprowadza kolejno [[test pierwszości]] dla liczb <math>N = 2, 3, 4, 5...</math> w następujący sposób. Program wykonuje pętlę, próbując podzielić liczbę ''N'' przez wszystkie możliwe dzielniki <math>d = N-1, N-2, \dots 1.</math> (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ść <math>n = 2^N 7^{d-1}</math> i wykonuje algorytm od nowa dla kolejnej wartości ''N''. Wartość <math>2^N 7^{d-1}</math> 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)<ref name="Guy1983">{{Cytuj pismo |nazwisko = Guy |imię = Richard K. |autor link = Richard Kenneth Guy |tytuł = Conway’s Prime Producing Machine |url = https://www.tandfonline.com/doi/abs/10.1080/0025570X.1983.11977011 |czasopismo = [[Mathematics Magazine]] |wolumin = 56 |wydanie = 1 |strony = 26–33 |rok = 1983 |wydawca = [[Taylor & Francis]] |doi = 10.1080/0025570X.1983.11977011 |język = en |data dostępu = 2022-01-06 |odn =}}</ref> bądź Havila (2007)<ref name="Havil2007" />.

Dotarcie do liczby pierwszej 2, 3, 5, 7... zajmuje temu programowi odpowiednio 19, 69, 281, 710,... kroków od momentu uruchomienia {{OEIS|id=A007547}}.

Istnieje także wariant programu Conwaya<ref name="Guy1983" /><ref name="Conway1996">{{cytuj książkę |nazwisko = Conway |imię = John H. |nazwisko2 = Guy |imię2 = Richard K. |tytuł = The Book of Numbers |język = en |wydawca = Copernicus |miejsce = New York |rok = 1996 |isbn = 978-1-4612-8488-8 |doi = 10.1007/978-1-4612-4072-3 |strony = 147 |data dostępu = 2021-09-02}}</ref>, który różni się od powyższej wersji dwoma ułamkami:
: <math>\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)</math>

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 {{OEIS|id=A007546}}. Pojedynczy przebieg programu, sprawdzający, czy liczba ''N'' jest pierwsza, wymaga następującej liczby kroków:
: <math>N - 1 + (6N+2)(N-b) + 2 \sum\limits^{N-1}_{d=b} \left\lfloor \frac{N}{d} \right\rfloor,</math>

gdzie <math>b < N</math> jest największym dzielnikiem całkowitym ''N'', a <math>\lfloor x \rfloor</math> jest [[Podłoga i sufit|częścią całkowitą]] ''x''<ref name="Havil2007" /><ref name="Guy1983" />.

W roku 1999 matematyk Devin Kilminster zademonstrował krótszy program znajdujący liczby pierwsze<ref name="Havil2007" />, składający się z dziesięciu instrukcji:
: <math>\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)</math>

Dla początkowego wejścia <math>n = 10</math> kolejne liczby pierwsze są otrzymywane jako wykładniki potęg liczby 10.
<!-- Warto sprawdzić działanie programu, by upewnić się, że nie ma literówki w źródle -->

== Uwagi ==
{{Uwagi}}

== Bibliografia ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{MathWorld|adres=FRACTRAN |tytuł=FRACTRAN |data dostępu=16 lipca 2021}}
* [http://www.esolangs.org/wiki/Fractran Fractran] – hasło na wiki Esolang
* {{Cytuj stronę |url = http://www.dev.gd/20130121-fun-with-john-conways-fractran.html |tytuł = Implementacja w języku Ruby i przykładowe programy |opublikowany = dev.gd |archiwum = https://web.archive.org/web/20130125232746/http://www.dev.gd/20130121-fun-with-john-conways-fractran.html |zarchiwizowano = 2013-01-25}} – blog programisty Johna Biesneckera
* [https://malisper.me/building-fizzbuzz-fractran-bottom/ Implementacja kompilatora do języka FRACTRAN w języku Lisp] – blog programisty Michaela Malisa
* {{Cytuj stronę |url = http://clomont.com/a-universal-fractran-interpreter-in-fractran/ |tytuł = Implementacja interpretera FRACTRAN w języku FRACTRAN |opublikowany = clomont.com |archiwum = https://web.archive.org/web/20180104084828/http://clomont.com/a-universal-fractran-interpreter-in-fractran/ |zarchiwizowano = 2018-01-04}} – blog programisty Chrisa Lomonta

[[Kategoria:Ezoteryczne języki programowania]]
[[Kategoria:Rozrywka matematyczna]]