28.03.2023 19:42
weird_overdramatic 4 1700 Источник

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

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

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

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

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

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

  1. пробуем умножить входное число на первую дробь

  2. если результат — натуральное число, оно становится новым входным числом, и алгоритм начинается с первого шага

  3. если результат — дробь, переходим к следующей дроби и пробуем аналогично

  4. когда дробей не осталось, программа останавливается

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

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

Здесь я и не буду рассматривать реализацию языка, скажу лишь, что ожидается, что в ней будет использоваться длинная арифметика. Примеры реализации на 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)

Результат: 2^{a-b}

Программа: \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й регистр мы добавляем bраз a, используя вложенный цикл и копирование регистра.

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 и оригинальная гипотеза Коллатца принадлежат к совершенно разным видам Коллатцевых игр, но сам факт, что существуют неразрешимые игры, наводит на мысль, что и сама гипотеза не обязана быть разрешимой.

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

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

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

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

  1. конечно, упомянутая выше Strange Code: Esoteric Languages That Make Programming Fun Again (честное слово, не имею к ней никакого отношения)

  2. лекция Джона Конвея, где он рассказывает и про FRACTRAN, и про гипотезу Коллатца

  3. статья в блоге какого-то чувака, которая, к сожалению, с момента создания потеряла всё форматирование

Комментарии (4)


  1. xi-tauw
    00.00.0000 00:00
    #25381788

    У меня гипотеза Коллатца всегда вызывала радостные эмоции, потому что она позволяет проводить такое доказательство.

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

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


    1. domix32
      00.00.0000 00:00
      #25384486

      Так и P \ne NPдоказать можно.


      1. domix32
        00.00.0000 00:00
        #25384522
        +1

        @Boomburumя кажется только что комментарий полный формул. Содержимое

        Так и $P \ne NP$ доказать можно.


        1. Boomburum
          00.00.0000 00:00
          #25384654
          +1

          Пересохранили и вроде ок стало )