Фрактран

[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

Comments

[juan_gandhi]

Поразительно.

[ex0_planet]

А не является ли эта конструкция просто красиво замаскированной subleq-машиной?

[spamsink]

Красиво. Очень короткая универсальная машина получилась.
Жаль, Тьюринг не дожил.

[spamsink]

Наоборот, пожалуй. Фрактран придуман в 1972 году.

"Размер числа неограничен."

[timka21213]

Эх, счастливчики!

[vak]

Тьюринг бы оценил, да. В принципе можно было бы некий простенький компилятор наваять на эту машинку.

[vak]

Аналог бесконечной ленты в машине Тьюринга.

[vak]

Одни целые числа, никаких хитростей. Великая вещь математика.

[vak]

Примерно в ту же степь, но нет, слишком много различий. Описание машины Фрактран много проще, чем subleq. А возможности каждой машинной команды шире. В машине subleq элементарная команда изменяет значение только одной ячейки. В Фрактране умножение на дробь может изменять сразу много ячеек (которые обозначены как a, b, c в вышеприведённых примерах).

[juan_gandhi]

Представление конечных множеств целых чисел в виде просто чисел. Классно. Интересно, на какой аксиоматике это работает. Скажем, последовательность Гудстейна будет сходиться? По идее, раз эквивалентно машине Тьюринга, то да.

у меня профессиональная травма на этот счёт

[timka21213]

наелся арифметики с произвольной точностью для чисел с плавающей точкой, пока работал исследователем на проекте ESPRIT BRA в 94/95 (gnu C++, gdb, STL, перегрузка операций, параллельное ядро, IEEE стандарты, оплимальные алгоритмы операций - вот это вот всё вместе взятое на конечных но неограниченных на старте вычислений мантиссе и показателе).

[juan_gandhi]

Какая прелесть!

(с) Кронекер

[timka21213]

«Бог создал целые числа, все остальное есть дело рук человеческих»

Re: (с) Кронекер

[vak]

Круто Кронекер сказанул! 😀 Сразу возникает масса интересных вопросов. Существуют ли целые числа? С точки зрения материализма, и в целом позитивизма, никаких чисел в природе нет. А значит, бог их не создавал. Или числа всё-таки существуют? Но в каком-то другом смысле, не так как физическая реальность.

[vak]

Понимаю твою чувствительность к предмету. 😀
Я имел дело с верификацией плавающей IEEE арифметики работая в MIPS в своё время. Не произвольная точность, но тоже не фунт изюму.
Нынче для произвольной точности, к счастью, имеем libgmpxx.

GMP мы пользовались и собственно писали v.2.0

[timka21213]

Но там в то время не было параллелизации, а нам критично было распараллелить на Sequent Symmetry и прочие процессорные гиперкубы.

Вот строчка о нашем проекте в мануале GMP: The development of floating point functions of GNU MP 2 was supported in part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO (POlynomial System SOlving). Наша часть называлась STURM

Не думаю, что там с тех пор произошла революция - фундаментальная математика наука консервативная!