Меню Главная Случайная статья Настройки FRACTRAN Материал из https://ru.wikipedia.org FRACTRAN — полный по Тьюрингу эзотерический язык программирования, предложенный Джоном Конвеем. Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом ${\displaystyle n}$. Программа запускается путём обновления целого числа ${\displaystyle n}$ следующим образом: для первой дроби ${\displaystyle f}$ в списке, для которой произведение ${\displaystyle n\cdot f}$ является целым числом, заменяется ${\displaystyle n}$ на ${\displaystyle n\cdot f}$ это правило повторяется до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на ${\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)}$ Начиная с ${\displaystyle n=2}$ эта программа генерирует следующую последовательность целых чисел[1]: 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … После 2 эта последовательность содержит следующие степени 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 }$ которые являются простыми степенями 2. Свойства Программа FRACTRAN может рассматриваться как тип машины Минского, где регистры хранятся в простых показателях в аргументе ${\displaystyle n}$. Используя нумерацию Гёделя, положительное целое число ${\displaystyle 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; однако есть непрямой способ это сделать путём создания инструкции, которая помещается после других инструкций, которые проверяют конкретную переменную. Примечания последовательность A007542 в OEIS последовательность A034785 в OEIS Ссылки «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  Fractran: A Ridiculous Logical Language with John Conway [2012] John Conway. FRACTRAN — a simple universal programming language for arithmetic (англ.) // Open Problems Commun. Comput.. — 1986. — P. 4–26. Дж. Конвей. Фрактран: простой универсальный язык программирования для арифметики (рус.) // в книге «Человек, который играл в математику. Сборник памяти Джона Конвея» / перевод Б. Р. Френкина. — 2023. — ISSN 978-5-4439-1787-0.