ФРАКТРАН - FRACTRAN

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

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

Конвей 1987 дает следующие формула для простых чисел во ФРАКТРАНЕ:^{[примечание 1]}

$${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}} ight)}$$

Начиная с п= 2, эта программа FRACTRAN генерирует следующую последовательность целых чисел:

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

После 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,, точек}$$

которые являются простыми степенями двойки.

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

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

С помощью Гёделевская нумерация, положительное целое число п может кодировать произвольное количество произвольно больших положительных целочисленных переменных.^{[заметка 2]} Значение каждой переменной кодируется как показатель степени простого числа в простые множители целого числа. Например, целое число

$${displaystyle 60 = 2 ^ {2} время 3 ^ {1} время 5 ^ {1}}$$

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

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

$${displaystyle f_ {1} = {frac {21} {20}} = {frac {3 imes 7} {2 ^ {2} imes 5 ^ {1}}}}$$

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

$${displaystyle 60cdot f_ {1} = 2 ^ {2} imes 3 ^ {1} imes 5 ^ {1} cdot {frac {3 imes 7} {2 ^ {2} imes 5 ^ {1}}} = 3 ^ {2} время 7 ^ {1}}$$

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

• Каждый раз, когда выполняется инструкция, проверяемые переменные также уменьшаются.
• Одна и та же переменная не может быть одновременно уменьшена и увеличена в одной инструкции (в противном случае дробная часть, представляющая эту инструкцию, не была бы в ее самые низкие сроки ). Поэтому каждая инструкция FRACTRAN использует переменные при их проверке.
• Команда FRACTRAN не может напрямую проверить, равна ли переменная 0 (однако, косвенный тест может быть реализован путем создания инструкции по умолчанию, которая помещается после других инструкций, проверяющих конкретную переменную).

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

Добавление

Простейшая программа FRACTRAN - это отдельная инструкция, например

$${displaystyle left ({frac {3} {2}} ight)}$$

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

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

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

Умножение

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

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

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

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

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

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

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

Со входом 2^а3^б эта программа производит вывод 5^ab. ^{[заметка 3]}

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

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

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

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

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

$${displaystyle 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}} ight)}$$

и ввод 2^п3^d11 производит вывод 5^q7^р куда п = qd + р и 0 ≤ р < d.

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

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

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

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

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

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

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

Примечания

Рекомендации

Смотрите также

• Компьютер с одной инструкцией

внешняя ссылка

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