Фрактран

[vak]

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

У машины имеется один регистр, хранящий положительное целое число. Назовём его N. Размер числа неограничен. При старте в регистр заносится входное значение, которое необходимо обработать.

Программа машины представляет собой последовательность дробей. К примеру, эта программа вычисляет наибольшее из двух целых чисел. Типа std::max() в Си++:

5/6 5/2 5/3

Выполнение программы происходит так.

1. Начинаем с первой дроби в программной последовательности.
2. Умножаем N на дробь из программы.
3. Если получилось целое число - запоминаем его в регистре N и начинаем программу сначала (то есть переходим к пункту 1).
4. Если целое число не получилось - забываем его и переходим к следующей дроби в программе (то есть к пункту 2).
5. Когда дробей больше не осталось - программа заканчивается и выдаёт результат на регистре N.

Элегантно, правда? Определение такой машины заметно проще, чем машина Тьюринга, машина Поста или другие концепции. Заметьте, что Фрактран не двоичная машина, не десятичная, и вообще здесь вопрос основания системы счисления не имеет смысла. Я в примерах использую десятичные числа, но для выполнения программы оно без разницы.

Глянем, как выполняется вышеприведённая программа вычисления максимума. К примеру, вычислим max(9, 7). Входные значения a и b надо подавать на вход в виде числа N = 2^a * 3^b. Для 9 и 7 это будет 2⁹ * 3⁷ = 1119744. Результат будет выдан в виде N = 5^c, где с = max(a, b). Вот последовательность смены значения регистра N.

1119744
933120
777600
648000
540000
450000
375000
312500
781250
1953125

Будет понятнее, если мы перепишем в виде степеней:

2⁹3⁷ ⟶ 2⁸3⁶5¹ (умножили на 5/6)
2⁸3⁶5¹ ⟶ 2⁷3⁵5² (умножили на 5/6)
2⁷3⁵5² ⟶ 2⁶3⁴5³ (умножили на 5/6)
2⁶3⁴5³ ⟶ 2⁵3³5⁴ (умножили на 5/6)
2⁵3³5⁴ ⟶ 2⁴3²5⁵ (умножили на 5/6)
2⁴3²5⁵ ⟶ 2³3¹5⁶ (умножили на 5/6)
2³3¹5⁶ ⟶ 2²3⁰5⁷ (умножили на 5/6)
2²3⁰5⁷ ⟶ 2¹3⁰5⁸ (умножили на 5/2)
2¹3⁰5⁸ ⟶ 2⁰3⁰5⁹ (умножили на 5/2)

Видим, что программа сначала в цикле уменьшает значения a и b, увеличивая c. Когда b уменьшилось до нуля, в другом цикле уменьшается значение, увеличивая c. На выходе получаем N = 1953125 = 5⁹. То есть 9 как max(9, 7).

Вот другая программа, написанная известным Джоном Конвеем (который придумал игру Жизнь). Программа вычисляет бесконечную последовательность простых чисел. Как она работает - читайте в википедии. Или смотрите лекцию самого Джона Конвея на ютубе.

17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1

Известно, что машина Фрактран полная по Тьюрингу. То есть по вычислительной способности она эквивалентна любому другому компьютеру. Фрактран имеет условные переходы, циклы и неограниченный объём памяти. Мало того, существует интерпретатор Фрактрана, написанный на самом Фрактране. Вот его бинарный код:

5/19, 1558654261983398483185/122130132904968017083, 
185/1822837804551761449, 4996917562403854655/41, 272365/67, 43/5, 
43/71, 125173/47, 145915005923554298917151/952809757913927, 
950886101246622507133/41426511213649, 160585150715989139597/13, 
8752951/23, 17/43, 17/29, 6409/47, 5/17, 31/53, 17042839/7, 1829/41, 
59/73, 331639/23, 4307/41, 89/59, 3713/31, 79/83, 268837/23, 31/79, 
8633/7, 101/97, 68579/11, 9797/13, 9797/47, 35/101, 9167/13, 103/107, 
1774381/47, 109/103, 109/113, 578899/23, 11227/13, 127/109, 127/131, 
16637/47, 16637/11, 1114679/61, 2/127, 5/2, 3/37