FRACTRAN

FRACTRAN — повна за Тюрінгом езотерична мова програмування, яку запропонував Джон Конвей.

Опис

Програма на FRACTRAN записується як упорядкований список додатних дробів разом з початковим початковим цілочисловим входом n. Програма запускається оновленням цілого числа n в такий спосіб:

1. для першого дробу ${\displaystyle f}$ у списку, для якого добуток ${\displaystyle n\cdot f}$ є цілим числом, замініть ${\displaystyle n}$ на ${\displaystyle n\cdot f}$
2. повторюйте це правило доти, поки жоден дріб у списку не видасть цілого числа при множенні на ${\displaystyle n}$, потім зупиніть.

Наприклад така програма генерує прості числа:

${\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)}$

Починаючи з n = 2, ця програма генерує таку послідовність цілих чисел:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … послідовність A007542 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Після 2 ця послідовність містить такі степені 2:

${\displaystyle 2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots }$ послідовність A034785 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

які є простими степенями 2.

Розуміння програми FRACTRAN

Програма FRACTRAN може розглядатися як тип машини Мінського, де регістри зберігаються в простих показниках в аргументі n.

Використовувати нумерацію Геделя, додатне ціле число n може кодувати довільне число довільно великих додатних цілочислових змінних. Значення кожної змінної кодується як показник простого числа в простій факторизації цілого числа. Наприклад, ціле число

${\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}}$

представляє стан регістра, в якому одна змінна (яку ми будемо називати ${\displaystyle v_{2}}$) містить значення 2, а дві інші змінні (${\displaystyle v_{3}}$ і ${\displaystyle v_{5}}$) містять значення 1. Всі інші змінні містять значення 0.

Програма FRACTRAN — це впорядкований список додатних дробів. Кожен дріб є інструкцією, яка перевіряє одну або кілька змінних, представлених основними факторами її знаменника. Наприклад:

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

перевіряє дві змінні ${\displaystyle v_{2}}$ і ${\displaystyle v_{5}}$. Якщо ${\displaystyle v_{2}\geq 2}$ і ${\displaystyle v_{5}\geq 1}$, то виконуються присвоєння ${\displaystyle v_{2}:=v_{2}-2}$, ${\displaystyle v_{5}:=v_{5}-1}$, ${\displaystyle v_{3}:=v_{3}+1}$, ${\displaystyle v_{7}:=v_{7}+1}$. Наприклад:

${\displaystyle 60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}}$

Оскільки програма FRACTRAN є просто списком дробів, ці інструкції перевірка-присвоєння є єдиними допустимими інструкціями в мові FRACTRAN. Крім того, застосовуються такі обмеження:

• Кожного разу, коли виконується інструкція, змінні, що перевіряються, також зменшуються.
• Одну і ту ж змінну не можна одночасно зменшити і збільшити в одній інструкції (в іншому випадку дріб, що представляє цю інструкцію, не буде нескоротним).
• Інструкція FRACTRAN нездатна безпосередньо перевірити, чи дорівнює змінна 0. Однак є непрямий спосіб це зробити, створивши інструкцію, яка поміщається після інших інструкцій, які перевіряють конкретну змінну.

Коментарі

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)}$
2. Нумерацію Геделя не можна безпосередньо застосувати для від'ємних цілих чисел, чисел з рухомою комою або текстових рядків, хоча можна домовитись щодо непрямого подання цих типів даних. Пропоновані розширення до FRACTRAN включають FRACTRAN++ [ 16 липня 2021 у Wayback Machine.] і Bag [ 16 липня 2021 у Wayback Machine.].

Примітки

Посилання

• «Prime Number Pathology: Fractran» [ 10 липня 2018 у Wayback Machine.]
• Weisstein, Eric W. FRACTRAN(англ.) на сайті Wolfram MathWorld.
• Prime Number Pathology [Архівовано 14 квітня 2013 у Archive.is]
• FRACTRAN [ 15 серпня 2021 у Wayback Machine.]
• Project Euler Problem 308 [ 9 липня 2021 у Wayback Machine.]
• «Building Fizzbuzz in Fractran from the Bottom Up» [ 26 квітня 2017 у Wayback Machine.]