ФРАКТРАН

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

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

Конвей 1987 дает следующую формулу для простых чисел в FRACTRAN: ^{[примечание 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}} \ 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 )

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

Понимание программы FRACTRAN [ править ]

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

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

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

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)

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

Инструкция FRACTRAN	Условие	Действие
${\frac {3}{2}}$	v2> 0	Вычесть 1 из v2 Добавить 1 к v3
	v2 = 0	Стоп

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

Умножение [ править ]

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

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

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

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

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

Инструкция FRACTRAN	Текущее состояние	Государственные индикаторы	Условие	Действие	Следующее состояние
${\frac {3}{7}}$	А	Никто	v7> 0	Вычесть 1 из v7 Добавить 1 к v3	А
${\frac {11}{2}}$			v7 = 0 и v2> 0	Вычтите 1 из v2	B
${\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}}$	B	v11, v13	v3> 0	Вычесть 1 из v3 Добавить 1 к v5 Добавить 1 к v7	B
${\frac {1}{11}}$	B	v11, v13	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 ^a 3 ^b эта программа производит вывод 5 ^ab . ^{[заметка 3]}

Вышеупомянутая программа FRACTRAN, вычисляющая 3 умножения на 2 (так что на входе и на выходе должно быть значение, потому что 3 умножения на 2 равно 6.

2^{3}\times 3^{2}=72

5^{6}

Вычитание и деление [ править ]

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

Инструкция FRACTRAN	Текущее состояние	Государственные индикаторы	Условие	Действие	Следующее состояние
${\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}$	А	v11, v13	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	B
${\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}$	B	v17, v19	v7> 0	Вычесть 1 из v7 Добавить 1 к v3	B
${\frac {11}{17}}$	B	v17, v19	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 ^d 11 дает выход 5 ^q 7 ^r, где n = qd + r и 0 ≤ r < d .

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

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

Другие примеры [ править ]

Следующая программа 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 . ^[1] Для входа 2 ^a его выход равен 13 ^{H ( a )} . Программу можно проанализировать следующим образом:

Инструкция FRACTRAN	Текущее состояние	Государственные индикаторы	Условие	Действие	Следующее состояние
${\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	B
${\frac {1}{5}}$			v2 = 0	Никто	B
${\frac {2}{3}}$	B	Никто	v3> 0	Вычесть 1 из v3 Добавить 1 к v2	B
${\frac {2\cdot 5}{7}}$			v3 = 0 и v7> 0	Вычесть 1 из v7 Добавить 1 к v2	А
${\frac {7}{2}}$			v3 = 0 и v7 = 0 и v2> 0	Вычтем 1 из v2, прибавим 1 к v7	B
			v2 = 0 и v3 = 0 и v7 = 0	Стоп

Заметки [ править ]

↑ В Книге Чисел Джон Конвей и Ричард Гай дали несколько иную последовательность: $\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)$
^ Нумерация по Гёделю не может использоваться напрямую для отрицательных целых чисел, чисел с плавающей запятой или текстовых строк, хотя могут быть приняты соглашения для косвенного представления этих типов данных. Предлагаемые расширения для FRACTRAN включают FRACTRAN ++ и Bag .
^ Аналогичный алгоритм умножения описан на странице Esolang FRACTRAN .

Ссылки [ править ]

^ Джон Баэз, Puzzle # 4 , The п -category кафе

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

См. Также [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с Fractran (языком программирования) .

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

[1] В Книге Чисел Джон Конвей и Ричард Гай дали несколько иную последовательность: $\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] Нумерация по Гёделю не может использоваться напрямую для отрицательных целых чисел, чисел с плавающей запятой или текстовых строк, хотя могут быть приняты соглашения для косвенного представления этих типов данных. Предлагаемые расширения для FRACTRAN включают FRACTRAN ++ и Bag .

[3] Аналогичный алгоритм умножения описан на странице Esolang FRACTRAN .

[4] Джон Баэз, Puzzle # 4 , The п -category кафе

[примечание 1]