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

Ссылки

• Weisstein, Eric W. "FRACTRAN". MathWorld.
• John Conway ]