FRACTRAN
FRACTRAN — полный по Тьюрингу эзотерический язык программирования, предложенный Джоном Конвеем.
Описание
[править | править код]Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом n. Программа запускается путём обновления целого числа n следующим образом:
- для первой дроби в списке, для которой произведение является целым числом, замените на
- повторяйте это правило до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на , затем остановите.
Например следующая программа генерирует простые числа:
Начиная с n = 2, эта программа генерирует следующую последовательность целых чисел:
После 2 эта последовательность содержит следующие степени 2:
которые являются простыми степенями 2.
Понимание программы FRACTRAN
[править | править код]Программа FRACTRAN может рассматриваться как тип машины Минского, где регистры хранятся в простых показателях в аргументе n.
Используя нумерацию Гёделя, положительное целое число n может кодировать произвольное число произвольно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель простого числа в простой факторизации целого числа. Например, целое число
представляет состояние регистра, в котором одна переменная (которую мы будем называть ) содержит значение 2, а две другие переменные ( и ) содержат значение 1. Все остальные переменные содержат значение 0.
Программа FRACTRAN — это упорядоченный список положительных дробей. Каждая дробь представляет собой инструкцию, которая проверяет одну или несколько переменных, представленных основными факторами её знаменателя. Например:
проверяет две переменные и . Если и , то выполняются присвоения , , , . Например:
Поскольку программа 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 Fractran: A Ridiculous Logical Language with John Conway [2012]