FRACTRAN

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

ОписаниеПравить

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

1. для первой дроби $f$$f$  в списке, для которой произведение $n\cdot <!--\; \cdot \; -->f$$n\cdot f$  является целым числом, замените $n$$n$  на $n\cdot <!--\; \cdot \; -->f$$n\cdot f$ 
2. повторяйте это правило до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на $n$$n$ , затем остановите.

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

$\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)$$\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:

$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 <!--\; \dots \; -->$$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\times <!--\; \times \; -->3^1\times <!--\; \times \; -->5^1$$60=2^{2}\times 3^{1}\times 5^{1}$ 

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

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

$f_1=\frac{21}{20}=\frac{3\times <!--\; \times \; -->7}{2^2\times <!--\; \times \; -->5^1}$$f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}$ 

проверяет две переменные $v_2$$v_{2}$  и $v_5$$v_{5}$ . Если $v_2\ge <!--\; \ge \; -->2$$v_{2}\geq 2$  и $v_5\ge <!--\; \ge \; -->1$$v_{5}\geq 1$ , то выполняются присвоения $v_2:=v_2-<!--\; -\; -->2$$v_{2}:=v_{2}-2$ , $v_5:=v_5-<!--\; -\; -->1$$v_{5}:=v_{5}-1$ , $v_3:=v_3+1$$v_{3}:=v_{3}+1$ , $v_7:=v_7+1$$v_{7}:=v_{7}+1$ . Например:

$60\cdot <!--\; \cdot \; -->f_1=2^2\times <!--\; \times \; -->3^1\times <!--\; \times \; -->5^1\cdot <!--\; \cdot \; -->\frac{3\times <!--\; \times \; -->7}{2^2\times <!--\; \times \; -->5^1}=3^2\times <!--\; \times \; -->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"
• 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"