ФРАКТРАН

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

1. для первой дроби f в списке, для которой nf является целым числом, замените n на nf
2. повторяйте это правило до тех пор, пока ни одна дробь в списке не даст целое число при умножении на n , затем остановитесь.

Конвей 1987 предлагает следующую программу FRACTRAN под названием PRIMEGAME, которая находит последовательные простые числа :

$$\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, программа FRACTRAN генерирует следующую последовательность целых чисел:

• 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (последовательность A007542 в OEIS )

После 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$$

(последовательность A034785 в OEIS )

Показательной частью этих степеней двойки являются простые числа: 2, 3, 5 и т. д.

Понимание программы FRACTRAN

Программу FRACTRAN можно рассматривать как тип регистровой машины , в которой регистры хранятся в простых показателях в аргументе n .

Используя нумерацию Гёделя , положительное целое число n может кодировать произвольное количество сколь угодно больших положительных целочисленных переменных. Значение каждой переменной кодируется как показатель степени простого числа при простой факторизации целого числа. Например, целое число

$$60=2^{2}\times 3^{1}\times 5^{1}$$

представляет состояние регистра, в котором одна переменная (которую мы назовем v2) содержит значение 2, а две другие переменные (v3 и v5) содержат значение 1. Все остальные переменные содержат значение 0.

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

$$f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}$$

тесты v2 и v5. Если $v_{2}\geq 2$ и $v_{5}\geq 1$, затем он вычитает 2 из v2 и 1 из v5 и добавляет 1 к v3 и 1 к v7. Например:

$$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 использует переменные при их проверке.
• Инструкция FRACTRAN не может напрямую проверить, равна ли переменная 0 (однако можно реализовать косвенную проверку, создав инструкцию по умолчанию, которая помещается после других инструкций, проверяющих конкретную переменную).

Создание простых программ

Дополнение

Простейшая программа FRACTRAN представляет собой одну команду, например

$$\left({\frac {3}{2}}\right)$$

Эту программу можно представить в виде (очень простого) алгоритма следующим образом:

ФРАКТРАН инструкция	Состояние	Действие
${\frac {3}{2}}$	v2 > 0	Вычтите 1 из v2 Добавить 1 в v3
	v2 = 0	Останавливаться

Учитывая первоначальный ввод формы $2^{a}3^{b}$, эта программа вычислит последовательность $2^{a-1}3^{b+1}$, $2^{a-2}3^{b+2}$и т. д., пока, в конце концов, после $a$ шагов, не остается множителей 2 и произведение с ${\frac {3}{2}}$ больше не дает целое число; затем машина останавливается с окончательным выводом $3^{a+b}$. Таким образом, он складывает два целых числа вместе.

Умножение

Мы можем создать «множитель», «проходя» через «сумматор». Для этого нам нужно ввести состояния в наш алгоритм. Этот алгоритм будет принимать число $2^{a}3^{b}$ и производить $5^{ab}$:

Текущее состояние	Состояние	Действие	Следующее состояние
А	v7 > 0	Вычтите 1 из v7 Добавить 1 в v3	А
	v7 = 0 и v2 > 0	Вычтите 1 из v2	Б
	v7 = 0 и v2 = 0 и v3 > 0	Вычтите 1 из v3	А
	v7 = 0 и v2 = 0 и v3 = 0	Останавливаться
Б	v3 > 0	Вычтите 1 из v3 Добавьте 1 к v5 Добавить 1 в v7	Б
	v3 = 0	Никто	А

Состояние B — это цикл, который добавляет v3 к v5, а также перемещает v3 в v7, а состояние A — это внешний цикл управления, который повторяет цикл в состоянии B v2 раза. Состояние A также восстанавливает значение v3 из v7 после завершения цикла в состоянии B.

Мы можем реализовать состояния, используя новые переменные в качестве индикаторов состояния. Индикаторами состояния для состояния B будут v11 и v13. Обратите внимание, что нам нужны два индикатора контроля состояния для одного цикла; основной флаг (v11) и вторичный флаг (v13). Поскольку каждый индикатор используется при каждом его тестировании, нам нужен вторичный индикатор, говорящий «продолжать в текущем состоянии»; этот вторичный индикатор заменяется обратно на первичный индикатор в следующей инструкции, и цикл продолжается.

Добавив в таблицу алгоритма умножения индикаторы состояния и инструкции FRACTRAN, мы имеем:

ФРАКТРАН инструкция	Текущее состояние	Состояние индикаторы	Состояние	Действие	Следующее состояние
${\frac {3}{7}}$	А	Никто	v7 > 0	Вычтите 1 из v7 Добавить 1 в v3	А
${\frac {11}{2}}$			v7 = 0 и v2 > 0	Вычтите 1 из v2	Б
${\frac {1}{3}}$			v7 = 0 и v2 = 0 и v3 > 0	Вычтите 1 из v3	А
			v7 = 0 и v2 = 0 и v3 = 0	Останавливаться
${\frac {5\cdot 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}$	Б	в11, в13	v3 > 0	Вычтите 1 из v3 Добавьте 1 к v5 Добавить 1 в v7	Б
${\frac {1}{11}}$			v3 = 0	Никто	А

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

$$\left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)$$

Со входом 2 ^а 3 ^б эта программа выдает результат 5 ^аб .

Вышеупомянутая программа FRACTRAN, вычисляющая 3 раза по 2 (так что ее входные данные $2^{3}\times 3^{2}=72$ и его вывод должен быть $5^{6}$ потому что 3×2 равно 6.

Вычитание и деление

Аналогичным образом мы можем создать «вычитатель» FRACTRAN, а повторяющиеся вычитания позволяют нам создать алгоритм «частного и остатка» следующим образом:

ФРАКТРАН инструкция	Текущее состояние	Состояние индикаторы	Состояние	Действие	Следующее состояние
${\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}$	А	в11, в13	v2 > 0 и v3 > 0	Вычтите 1 из v2 Вычтите 1 из v3 Добавить 1 в v7	А
${\frac {1}{3\cdot 11}}$			v2 = 0 и v3 > 0	Вычтите 1 из v3	Х
${\frac {5\cdot 17}{11}}$			v3 = 0	Добавьте 1 к v5	Б
${\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}$	Б	в17, в19	v7 > 0	Вычтите 1 из v7 Добавить 1 в v3	Б
${\frac {11}{17}}$			v7 = 0	Никто	А
${\frac {1}{3}}$	Х		v3 > 0	Вычтите 1 из v3	Х
			v3 = 0	Останавливаться

Записав программу FRACTRAN, мы имеем:

$$\left({\frac {91}{66}},{\frac {11}{13}},{\frac {1}{33}},{\frac {85}{11}},{\frac {57}{119}},{\frac {17}{19}},{\frac {11}{17}},{\frac {1}{3}}\right)$$

и вход 2 ^н 3 ^д 11 производит результат 5 ^д 7 ^р где n = qd + r и 0 ≤ r < d .

Простой алгоритм Конвея

Приведенный выше алгоритм генерации простых чисел Конвея по сути представляет собой алгоритм частного и остатка в двух циклах. Учитывая ввод формы $2^{n}7^{m}$ где 0 ≤ m < n , алгоритм пытается разделить n +1 на каждое число от n до 1, пока не найдет наибольшее число k, которое является делителем n +1. Затем он возвращает 2 ^{п +1} 7 ^{к -1} и повторяется. Единственный раз, когда последовательность номеров состояний, сгенерированная алгоритмом, дает степень 2, - это когда k равен 1 (так что показатель степени 7 равен 0), что происходит только в том случае, если показатель степени 2 является простым числом. Пошаговое объяснение алгоритма Конвея можно найти у Havil (2007).

Для этой программы достижение простых чисел 2, 3, 5, 7... требует соответственно 19, 69, 281, 710,... шагов (последовательность A007547 в OEIS ).

Существует также вариант программы Конвея. который отличается от приведенной выше версии на две дроби:

$$\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}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)$$

Этот вариант немного быстрее: достижение 2, 3, 5, 7... занимает 19, 69, 280, 707... шагов (последовательность A007546 в OEIS ). Одна итерация этой программы, проверяющая конкретное число N на простоту, занимает следующее количество шагов:

$$N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,$$

где $b<N$ является наибольшим целым делителем N и $\lfloor x\rfloor$ это функция пола .

В 1999 году Девин Килминстер продемонстрировал более короткую программу из десяти инструкций:

$$\left({\frac {7}{3}},{\frac {99}{98}},{\frac {13}{49}},{\frac {39}{35}},{\frac {36}{91}},{\frac {10}{143}},{\frac {49}{13}},{\frac {7}{11}},{\frac {1}{2}},{\frac {91}{1}}\right).$$

Для начального ввода n = 10 последовательных простых чисел генерируются последующими степенями 10.

Другие примеры

Следующая программа FRACTRAN:

$$\left({\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}},{\frac {13}{2\cdot 5}},{\frac {1}{5}},{\frac {2}{3}},{\frac {2\cdot 5}{7}},{\frac {7}{2}}\right)$$

вычисляет вес Хэмминга H( a ) двоичного разложения a, т.е. количество единиц в двоичном разложении a . Учитывая ввод 2 ^а , его выход равен 13 ^{Ч( а )} . Программу можно проанализировать следующим образом:

ФРАКТРАН инструкция	Текущее состояние	Состояние индикаторы	Состояние	Действие	Следующее состояние
${\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}}$	А	v5, v11	v2 > 1	Вычтите 2 из v2 Добавить 1 в v3	А
${\frac {13}{2\cdot 5}}$			v2 = 1	Вычтите 1 из v2 Добавить 1 в v13	Б
${\frac {1}{5}}$			v2 = 0	Никто	Б
${\frac {2}{3}}$	Б	Никто	v3 > 0	Вычтите 1 из v3 Добавить 1 к версии 2	Б
${\frac {2\cdot 5}{7}}$			v3 = 0 и v7 > 0	Вычтите 1 из v7 Добавить 1 к версии 2	А
${\frac {7}{2}}$			v3 = 0 и v7 = 0 и v2 > 0	Вычтите 1 из v2 добавить 1 к v7	Б
			v2 = 0 и v3 = 0 и v7 = 0	Останавливаться

См. также

• Компьютер с одним набором команд
• Гипотеза Коллатца

Ссылки

• Гай, Ричард К. (1983). «Основная производственная машина Конвея» . Журнал «Математика» . 56 (1). Тейлор и Фрэнсис : 26–33. дои : 10.1080/0025570X.1983.11977011 .
• Конвей, Джон Х. (1987). «FRACTRAN: простой универсальный язык программирования для арифметики». Открытые проблемы коммуникации и вычислений . Springer-Verlag New York, Inc., стр. 4–26. дои : 10.1007/978-1-4612-4808-8_2 . ISBN  978-1-4612-9162-6 .
• Конвей, Джон Х.; Гай, Ричард К. (1996). Книга чисел . Springer-Verlag New York, Inc. ISBN  0-387-97993-Х .
• Хэвил, Джулиан (2007). В замешательстве! . Издательство Принстонского университета. ISBN  978-0-691-12056-0 .
• Робертс, Шивон (2015). «Критерии добродетели». Гений в игре - Пытливый ум Джона Хортона Конвея . Блумсбери. стр. 115–119. ISBN  978-1-62040-593-2 .

Внешние ссылки

• Лекция Джона Конвея: «Фрактран: смешной логический язык»
• «Патология простых чисел: фрактран»
• Вайсштейн, Эрик В. «ФРАКТРАН» . Математический мир .
• Патология простых чисел
• ФРАКТРАН — (Esolang wiki)
• Реализация Ruby и примеры программ
• Задача Эйлера 308 проекта
• «Создание Fizzbuzz во Fractran снизу вверх»
• Крис Ломонт, «Универсальный интерпретатор FRACTRAN во FRACTRAN»