Сразу предупреждаю, те, кто учили CS в ВУЗе могут дальше не читать, интересно не будет. Статья больше для программистов-самоучек без формального образования (вроде меня самого), которые не против узнать какой-нибудь интересный факт из теоретической computer science.
Все наверняка слышали об алгоритмически-неразрешимых задачах. Эти задачи многие воспринимают как что-то очень далёкое и очень теоретическое. Между тем наткнуться на одну из них в обычной жизни не так уж и сложно.
Для написания брейнфаковской части мультиквайна из статьи Мультиязыковые квайны я воспользовался следующей функцией:
def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])
Это самый простой, но при этом самый длинный и неэффективный способ, распечатать заданную строку на Brainfuck (как оказалось, Юсукэ Эндо, в своём уроборосе использовал его же):
>>> brainfuck("Hello world!")
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++.>'
Разумеется захотелось сделать более умную функцию, которая позволила бы мне за счёт небольшого увеличения питоновской части квайна сильно уменьшить брейнфаковскую.
Сразу напрашивался вариант где после печати очередного символа не переходим на следующую, пустую ячейку ленты, а вычисляем очередной символ как смещение от предыдущего:
def brainfuck(st):
cur=0
result=''
for l in st:
diff=ord(l)-cur
if diff>0: result+='+'*abs(diff)
if diff<0: result+='-'*abs(diff)
result+='.'
cur=ord(l)
return result
>>> brainfuck("Hello world!")
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.--------.+++.------.--------.-------------------------------------------------------------------.'
Стало значительно лучше. Когда я подставил эту новую функцию в квайн, размер брейнфаковской части квайна уменьшился в 1.6 раз. Потом я посмотрел на каноничный пример выводящий 'Hello world' и понял, что, мягко говоря, ещё есть над чем работать:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++. >.+++.------.--------.>+.>.
Кроме этого, я увидел, что у меня не получается сходу формализовать устройство этой простенькой программы. Как она работает — вполне понятно (часть программы до знака "]" заполняет на ленте 4 ячейки кодами близкими к кодам букв фразы, а остальная часть программы — finetuning, перемещаемся между символами, тут и там слегка обрабатываем напильником и выводим), а вот как написать программу, которая выдаст её на выходе…
И задался я вопросом — а как написать программу, которая получает строку и выдаёт минимальную программу на brainfuck, которая эту строку выводит. Те, кто учил CS и всё-таки дочитал до этого места сейчас ухмыляются…
Оказалось, что это невозможно. Не потому, что я слабый программист, не из-за того, что такая программа требует каких-то сумасшедших объёмов данных и/или невероятных вычислительных ресурсов. Она просто невозможна, это одно из фундаментальных ограничений нашей несовершенной вселенной. Сейчас приведу доказательство, не строгое, но надеюсь, хотя бы понятное.
Объяснять буду уже на Питоне, т.к. писать нетривиальный код на брейнфаке не умею, да и пониманию доказательства он вряд ли поспособствует, впрочем всё это работает для любого полного по тьюрингу языка программирования.
Итак, докажем от противного. Допустим, путём невероятных усилий нам удалось создать функцию minimal_program, которая получает строку и возвращает код модуля на Питоне, который печатает эту строку, причём этот модуль гарантированно минимально возможного размера.
создадим модуль, в этом модуле будет функция minimal_program, будет вспомогательная функция generate_strings, которая генерирует все возможные строки — сначала строки из одного символа в алфавитном порядке, потом из двух, из трёх и т.д. и будет следующая функция:
def large_string(n):
for st in generate_strings():
mp=minimal_program(st)
if len(mp)>=n:
return st
Понятно, что эта функция делает — она возвращает строку, для вывода которой нужен модуль размером не менее n символов. А теперь вычисляем размер получившегося модуля, обозначим его MODULE_LEN и дописываем в наш модуль несколько строк:
if "__main__"==__name:
print large_string(MODULE_LEN*1000)
Итого, что мы имеем? Программу, размером чуть больше MODULE_LEN, которая выводит строку, минимальная программа для вывода которой не может быть меньше MODULE_LEN*1000. Пришли к противоречию, чем доказали невозможность исходной посылки — возможности существования функции minimal_program.
Кстати, это доказательство — совсем не повод не пытаться создавать хорошие алгоритмы архивации и писать генераторы короткого кода на brainfuck (я сам ещё точно попробую)! Просто задачу нужно ставить несколько менее глобальную.
Ссылки для тех, кто хочет углубиться в тему:
Алгоритмически неразрешимые задачи
Колмогоровская сложность
Автор: gromozeka1980
