FRACTRAN

FRACTRAN — полный по Тьюрингу эзотерический язык программирования, предложенный Джоном Конвеем.

Описание

Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом n Программа запускается путём обновления целого числа n следующим образом:

Например следующая программа генерирует простые числа:

( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 2 , 1 7 , 55 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}{2}},{frac {1}{7}},{frac {55}{1}}
ight)}

Начиная с n = 2, эта программа генерирует следующую последовательность целых чисел:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … последовательность A007542 в 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 , … {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 может кодировать произвольное число произвольно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель простого числа в простой факторизации целого числа. Например, целое число

60 = 2 2 × 3 1 × 5 1 {displaystyle 60=2^{2} imes 3^{1} imes 5^{1}}

представляет состояние регистра, в котором одна переменная (которую мы будем называть v 2 {displaystyle v_{2}} ) содержит значение 2, а две другие переменные ( v 3 {displaystyle v_{3}} и v 5 {displaystyle v_{5}} ) содержат значение 1. Все остальные переменные содержат значение 0.

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

f 1 = 21 20 = 3 × 7 2 2 × 5 1 {displaystyle f_{1}={frac {21}{20}}={frac {3 imes 7}{2^{2} imes 5^{1}}}}

проверяет две переменные v 2 {displaystyle v_{2}} и v 5 {displaystyle v_{5}} . Если v 2 ≥ 2 {displaystyle v_{2}geq 2} и v 5 ≥ 1 {displaystyle v_{5}geq 1} , то выполняются присвоения v 2 := v 2 − 2 {displaystyle v_{2}:=v_{2}-2} , v 5 := v 5 − 1 {displaystyle v_{5}:=v_{5}-1} , v 3 := v 3 + 1 {displaystyle v_{3}:=v_{3}+1} , v 7 := v 7 + 1 {displaystyle v_{7}:=v_{7}+1} . Например:

60 ⋅ f 1 = 2 2 × 3 1 × 5 1 ⋅ 3 × 7 2 2 × 5 1 = 3 2 × 7 1 {displaystyle 60cdot f_{1}=2^{2} imes 3^{1} imes 5^{1}cdot {frac {3 imes 7}{2^{2} imes 5^{1}}}=3^{2} imes 7^{1}}

Поскольку программа FRACTRAN представляет собой просто список дробей, эти инструкции проверка-присвоение являются единственными допустимыми инструкциями на языке FRACTRAN. Кроме того, применяются следующие ограничения:

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