Представьте, что где-то в другой вселенной инопланетяне тоже изобрели вычислительную машину. Двоичная логика их не впечатлила, зато в силу неких особенностей у инопланетян нет проблем с умножением и делением. Поэтому машина получилась несколько странная.
У машины имеется один регистр, хранящий положительное целое число. Назовём его N. Размер числа неограничен. При старте в регистр заносится входное значение, которое необходимо обработать.
Программа машины представляет собой последовательность дробей. К примеру, эта программа вычисляет наибольшее из двух целых чисел. Типа std::max() в Си++:
5/6 5/2 5/3
Выполнение программы происходит так.
- Начинаем с первой дроби в программной последовательности.
- Умножаем N на дробь из программы.
- Если получилось целое число - запоминаем его в регистре N и начинаем программу сначала (то есть переходим к пункту 1).
- Если целое число не получилось - забываем его и переходим к следующей дроби в программе (то есть к пункту 2).
- Когда дробей больше не осталось - программа заканчивается и выдаёт результат на регистре N.
Элегантно, правда? Определение такой машины заметно проще, чем
машина Тьюринга,
машина Поста или другие концепции. Заметьте, что Фрактран не двоичная машина, не десятичная, и вообще здесь вопрос основания системы счисления не имеет смысла. Я в примерах использую десятичные числа, но для выполнения программы оно без разницы.
Глянем, как выполняется вышеприведённая программа вычисления максимума. К примеру, вычислим max(9, 7). Входные значения a и b надо подавать на вход в виде числа N = 2
a * 3
b. Для 9 и 7 это будет 2
9 * 3
7 = 1119744. Результат будет выдан в виде N = 5
c, где с = max(a, b). Вот последовательность смены значения регистра N.
1119744
933120
777600
648000
540000
450000
375000
312500
781250
1953125
Будет понятнее, если мы перепишем в виде степеней:
2937 ⟶ 283651 (умножили на 5/6)
283651 ⟶ 273552 (умножили на 5/6)
273552 ⟶ 263453 (умножили на 5/6)
263453 ⟶ 253354 (умножили на 5/6)
253354 ⟶ 243255 (умножили на 5/6)
243255 ⟶ 233156 (умножили на 5/6)
233156 ⟶ 223057 (умножили на 5/6)
223057 ⟶ 213058 (умножили на 5/2)
213058 ⟶ 203059 (умножили на 5/2)
Видим, что программа сначала в цикле уменьшает значения a и b, увеличивая c. Когда b уменьшилось до нуля, в другом цикле уменьшается значение, увеличивая c. На выходе получаем N = 1953125 = 5
9. То есть 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
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
