К гипотезе Коллатца через эзолэнг Джона Конвея29.03.2023 08:02

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

Одним из интересных (на мой субъективный взгляд) эзолэнгов является FRACTRAN, концепция которого была предложена Джоном Конвеем (известным в первую очередь конечно же благодаря игре «Жизнь»).

В этой статье я расскажу про клёвую математику, лежащую в основе этого эзотерического языка программирования, разберу несколько простых программ на нём, и, наконец, покажу связь FRACTRAN’а с гипотезой Коллатца. Статья во многом является вольным пересказом соответствующей главы книги Strange Code: Esoteric Languages That Make Programming Fun Again (которую я бы рекомендовал всем, кто хочет взглянуть на программирование под другим углом).

Спецификация

Начать конечно стоит с логики, лежащей в основе этого языка.

Программа представляет из себя последовательность обыкновенных дробей (рациональных чисел), на вход она принимает единственное натуральное число. Алгоритм выполнение программы следующий:

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

Результатом выполнения программы является последнее целое число (или, при желании, все промежуточные целые числа).

Простыми словами: ищется первая по порядку дробь, умножение на которую даёт целое число. Если такая дробь найдена — результат умножения становится новым входным числом и алгоритм начинается с начала (с первой дроби), если такой дроби не найдено — программа останавливается.

Здесь я и не буду рассматривать реализацию языка, скажу лишь, что ожидается, что в ней будет использоваться длинная арифметика. Примеры реализации на python’е можно легко найти в интернете, нас интересует не это.

Сложение чисел и машина Минского

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

$\left( \frac{3}{2} \right)$

Если мы «запустим» эту программу и дадим на вход 144, результат будет 729 (входное число умножается на полтора, пока оно является целым). Разберёмся, какие же два числа мы тут складываем, и что за результат получаем.

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

Отмотаем немного назад. Как нам говорит основная теорема арифметики, каждое число можно единственным образом разложить на простые множители. Например, наше 144 выше — это 2^4 * 3^2 , соответственно, в регистре №2 хранится 4, в регистре №3 (номер регистра соответствует простому числу, «отвечающему» за него) — 2. Результат выполнения программы — 729— не что иное, как 3^6 .

Что это значит? Что наша программа принимает на вход число в формате 2^a*3^b , а в результате выдаёт $3^{a+b}$ , то есть установив значения регистров №2 и №3 как a и b соответственно, результатом выполнения программы будет их сумма в 3 м регистре.

Очевидно, что вместо регистров 2 и 3 можно использовать два любых других простых m и n, соответственно, входное число должно быть в формате m^a*n^b , а программа примет вид $\left( \frac{m}{n} \right)$ , результат будет записан в регистр m.

Больше примеров

Не хочется сильно раздувать статью вдаваясь в специфику языка, поэтому вот еще несколько примеров с кратким объяснением их работы:

Вычитание

Входные данные: $2^a*3^b \; (a>b)» src=«https://habrastorage.org/getpro/habr/upload_files/615/27b/f5b/61527bf5b12427be69966259a19c6fa3.svg» /></p> <p><em>Результат</em>: <img alt=$

Программа: $\left( \frac{1}{6} \right)$

Тут всё аналогично со сложением, мы уменьшаем одновременно 2й и 3й регистры, пока в 3 м не окажется 0, в результате во 2 м получаем искомую разницу.

max (a, b)

Входные данные: 2^a*3^b

Результат: $5^{max(a,b)}$

Программа: $\left( \frac{5}{6} ; \frac{5}{2} ; \frac{5}{3}\right)$

Наконец, программа, в которой больше одной дроби! Что же здесь происходит? Сначала, мы увеличиваем 5й регистр, пока наше входное число делится на 6. В результате, после первого шага, минимальное число перемещается в 5й регистр, а в регистре с максимальным числом оказывается их (чисел) разница. Вторая и третья дроби по очередь тестируют 2й и 3й регистры на то, осталось ли там что-то еще, и переносят этот остаток в 5й регистр. В результате изначальные регистры остаются пустыми, а в 5 м оказывается искомый максимум.

Копирование регистра

Входные данные: 2^a*7^1

Результат: 2^a*3^a

Программа: $\left( \frac{165}{14} ; \frac{7}{11} ; \frac{13}{7} ; \frac{34}{65} ; \frac{13}{17} ; \frac{1}{13} \right)$

В этом примере дроби 7/11 и 13/17 являются аналогами цикла в привычных языках программирования. Рассмотрим блок из первых двух дробей подробнее: 165 = 3 * 5 *11 , каждое умножение входного числа на первую дробь уменьшает значение во 2 м регистре на 1, одновременно увеличивая 3й и 5й (и 11й, но это не так важно1) регистры так же на 1. Поскольку 7 входит во входное число в 1й степени, умножение на 1ю дробь происходит только один раз. После чего единица перемещается из 7 го регистра в 11й. Вторая дробь (7/11) перемещает эту единицу обратно. Происходит это до тех пор, пока входное число делится на 2 (значение во 2 м регистре больше нуля). После этого 3я дробь (13/7) перемещает единицу из 7 го регистра в 13й, и начинается второй цикл по перемещению значения из 5 го регистра обратно во 2й, очищенный в первом цикле. Последняя дробь (1/13) очищает 13й регистр.

Умножение

Входные данные: 2^a*3^b

Результат: $5^{ab}$

Программа: $\left( \frac{455}{22} ; \frac{11}{13} ; \frac{1}{11} ; \frac{2}{7} ; \frac{11}{3} ; \frac{1}{2} \right)$

В предыдущем примере мы узнали, как во FRACTRAN’е выглядит цикл. Принцип умножения основан на нём же. В 5й регистр мы добавляем раз , используя вложенный цикл и копирование регистра.

PRIMEGAME Джона Конвея

Входные данные: 2^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ки с простым показателем. Объяснение можно найти в лекции самого Конвея, ссылка на которую есть в конце статьи.

Так при чём здесь гипотеза Коллатца?

Первым делом, перепишем уравнение, задающее гипотезу, в чуть другой форме. Оригинальное выглядит следующим образом:

$x_{i+1} = \begin{cases} x_i/2, x_i \vdots 2 \\ 3x_i + 1, иначе \end{cases}$

Если результат деления на 2 даёт нам целое число, оно становится новым входным числом, иначе, применяем второе преобразование. Запишем это в таком виде:

$x_{i+1}=x_i/2 \: | \: 3x_i+1$

В общем виде это выглядит следующим образом:

$x_{i+1} = g(x_i) = g_1(x_i) \: | \: g_2(x_i), где \: g_j(x) = a_jx+b_j$

Функция g(x) возвращает самое первое целое число, полученное при вычислении функций g_1 и g_2 . Но совершенно необязательно ограничивать g(n) двумя частями, представим самый общий вид такой функции:

$g(n) = g_1(n)\:|\:g_2(n)\:|\:g_3(n)\:|\: \cdots \:|\: g_k(n)$

Конвей назвал такие функции Коллатцевыми играми (в оригинале Collatzian games). Заметим, что если для всех функций g_i взять b_i=0 , получится не что иное, как программа на FRACTRAN’е!

И это еще не всё

Поскольку FRACTRAN представляет из себя машину Минского, он является полным по Тьюрингу, а значит, на него распространяется проблема остановки. Поскольку программа на FRACTRAN’е — это частный случай Коллатцевой игры, значит, существуют такие игры, для которых невозможно доказать, закончатся ли они для всевозможных входных данных. Это и есть главный вывод этой статьи.

Еще раз, гипотеза Коллатца и FRACTRAN — два частных случая Коллатцевой игры. При этом игра, описываемая через FRACTRAN, неразрешима.

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

Вместо заключения

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

Во-вторых, надеюсь, кому-нибудь этот путь тоже показался интересным, поэтому…

Полезные ссылки

конечно, упомянутая выше Strange Code: Esoteric Languages That Make Programming Fun Again (честное слово, не имею к ней никакого отношения)
лекция Джона Конвея, где он рассказывает и про FRACTRAN, и про гипотезу Коллатца
статья в блоге какого-то чувака, которая, к сожалению, с момента создания потеряла всё форматирование