Русская Википедия:FRACTRAN
FRACTRAN — полный по Тьюрингу эзотерический язык программирования, предложенный Джоном Конвеем.
Описание
Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом n. Программа запускается путём обновления целого числа n следующим образом:
- для первой дроби <math>f</math> в списке, для которой произведение <math>n\cdot f</math> является целым числом, замените <math>n</math> на <math>n\cdot f</math>
- повторяйте это правило до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на <math>n</math>, затем остановите.
Например следующая программа генерирует простые числа:
- <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>
Начиная с n = 2, эта программа генерирует следующую последовательность целых чисел:
- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... Шаблон:OEIS
После 2 эта последовательность содержит следующие степени 2:
- <math>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</math> Шаблон:OEIS
которые являются простыми степенями 2.
Понимание программы FRACTRAN
Программа FRACTRAN может рассматриваться как тип машины Минского, где регистры хранятся в простых показателях в аргументе n.
Используя нумерацию Гёделя, положительное целое число n может кодировать произвольное число произвольно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель простого числа в простой факторизации целого числа. Например, целое число
- <math>60 = 2^2 \times 3^1 \times 5^1</math>
представляет состояние регистра, в котором одна переменная (которую мы будем называть <math>v_2</math>) содержит значение 2, а две другие переменные (<math>v_3</math> и <math>v_5</math>) содержат значение 1. Все остальные переменные содержат значение 0.
Программа FRACTRAN — это упорядоченный список положительных дробей. Каждая дробь представляет собой инструкцию, которая проверяет одну или несколько переменных, представленных основными факторами её знаменателя. Например:
- <math>f_1 = \frac{21}{20} = \frac{3 \times 7}{2^2 \times 5^1}</math>
проверяет две переменные <math>v_2</math> и <math>v_5</math>. Если <math>v_2 \ge 2</math> и <math>v_5 \ge 1</math>, то выполняются присвоения <math>v_2:=v_2-2</math>, <math>v_5:=v_5-1</math>, <math>v_3:=v_3+1</math>, <math>v_7:=v_7+1</math>. Например:
- <math>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</math>
Поскольку программа FRACTRAN представляет собой просто список дробей, эти инструкции проверка-присвоение являются единственными допустимыми инструкциями на языке FRACTRAN. Кроме того, применяются следующие ограничения:
- Каждый раз, когда выполняется инструкция, проверяемые переменные также уменьшаются.
- Одна и та же переменная не может быть одновременно уменьшена и увеличена в одной инструкции (в противном случае дробь, представляющая эту инструкцию, не будет несократимой).
- Инструкция FRACTRAN неспособна непосредственно проверить, равна ли переменная 0. Однако есть непрямой способ это сделать путём создания инструкции, которая помещается после других инструкций, которые проверяют конкретную переменную.
Ссылки
- "Prime Number Pathology: Fractran"
- Weisstein, Eric W. "FRACTRAN". MathWorld.
- Prime Number Pathology
- FRACTRAN
- Ruby implementation and example programs
- Project Euler Problem 308
- "Building Fizzbuzz in Fractran from the Bottom Up"
- Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"
- John Conway Шаблон:YouTube
