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

Jeśli na wejściu zostanie podana liczba 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: (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 FRACTRANEdytuj

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

 

sprawdza zawartość v2 i v5. Jeśli   i   instrukcja   odejmie 2 od v2 i 1 od v5 oraz doda 1 do v3 i 1 do v7. Na przykład:

 

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

Przykładowe programy FRACTRANEdytuj

DodawanieEdytuj

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

 

Program ten oblicza sumę dwóch liczb całkowitych,   i   Dla początkowej wartości   program generuje sekwencję     itd., aż w końcu, po   krokach, program zatrzyma się z końcowym wynikiem  

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

 

Dla wejściowej wartości   program zatrzyma się z wynikiem   Dzięki temu informacja o wartościach   i   nie zostaje zniszczona.

W tym wariancie zmienna v5 tymczasowo przechowuje początkową wartość v3 =   Pierwsza instrukcja   przenosi zawartość v3 do v2 oraz v5; gdy v3 osiągnie wartość zero, program zaczyna wykonywać drugą instrukcję   która odtwarza wartość v3 z v5.

Mnożenie – przykład pętliEdytuj

Następujący program[2] przyjmuje na wejściu liczbę   i zatrzymuje się z końcowym wynikiem   tym samym obliczając wynik mnożenia  

 

Działanie programu polega na wykonywaniu procedury dodającej w pętli, tak, by dodać   do   dokładnie   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:

 

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

  • w chwili początkowej (wejściowa wartość  ) 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   a zawartość v7 maleje o 1. Gdy v7 osiąga zero, program zatrzymuje się.

Algorytm generowania liczb pierwszych (PRIMEGAME)Edytuj

Zaprezentowany na wstępie program PRIMEGAME, po wprowadzeniu na wejściu liczby   przeprowadza kolejno test pierwszości dla liczb   w następujący sposób. Program wykonuje pętlę, próbując podzielić liczbę N przez wszystkie możliwe dzielniki   (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ść   i wykonuje algorytm od nowa dla kolejnej wartości N. Wartość   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   A007547 w OEIS).

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

 

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   A007546 w OEIS). Pojedynczy przebieg programu, sprawdzający, czy liczba N jest pierwsza, wymaga następującej liczby kroków:

 

gdzie   jest największym dzielnikiem całkowitym N, a   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:

 

Dla początkowego wejścia   kolejne liczby pierwsze są otrzymywane jako wykładniki potęg liczby 10.

UwagiEdytuj

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

BibliografiaEdytuj

  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ętrzneEdytuj