FRACTRAN

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

Опис

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

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

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

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

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

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … Шаблон:OEIS

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

$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$ Шаблон:OEIS

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

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

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

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

$60=2^2\times 3^1\times 5^1$

представляє стан регістра, в якому одна змінна (яку ми будемо називати $v_2$) містить значення 2, а дві інші змінні ($v_3$ і $v_5$) містять значення 1. Всі інші змінні містять значення 0.

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

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

перевіряє дві змінні $v_2$ і $v_5$. Якщо $v_2\ge 2$ і $v_5\ge 1$, то виконуються присвоєння $v_2:=v_2-2$, $v_5:=v_5-1$, $v_3:=v_3+1$, $v_7:=v_7+1$. Наприклад:

$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. Однак є непрямий спосіб це зробити, створивши інструкцію, яка поміщається після інших інструкцій, які перевіряють конкретну змінну.

Посилання

• «Prime Number Pathology: Fractran» Шаблон:Webarchive
• Шаблон:MathWorld
• Prime Number Pathology Шаблон:Webarchive
• FRACTRAN Шаблон:Webarchive
• Ruby implementation and example programs
• Project Euler Problem 308 Шаблон:Webarchive
• «Building Fizzbuzz in Fractran from the Bottom Up» Шаблон:Webarchive
• Chris Lomont, «A Universal FRACTRAN Interpreter in FRACTRAN»