FRACTRAN — полный по Тьюрингу эзотерический язык программирования, предложенный Джоном Конвеем.
Программа на FRACTRAN записывается как упорядоченный список положительных дробей вместе с начальным положительным целочисленным входом . Программа запускается путём обновления целого числа следующим образом: для первой дроби в списке, для которой произведение является целым числом, заменяется на это правило повторяется до тех пор, пока ни одна дробь в списке не выдаст целое число при умножении на , затем останавливается.
Например следующая программа генерирует простые числа:
Начиная с эта программа генерирует следующую последовательность целых чисел: 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … После 2 эта последовательность содержит следующие степени 2:
которые являются простыми степенями 2.
Свойства Программа FRACTRAN может рассматриваться как тип машины Минского, где регистры хранятся в простых показателях в аргументе .
Используя нумерацию Гёделя, положительное целое число может кодировать произвольное число произвольно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель простого числа в простой факторизации целого числа. Например, целое число:
представляет состояние регистра, в котором одна переменная (которую мы будем называть ) содержит значение 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
Категория:Математические головоломки и досуг Категория:Эзотерические языки программирования Категория:Модели вычислений Категория:Джон Конвей