о невычислимых функциях

falcao — 07.03.2021 Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля".

Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.

Поскольку мы будем говорить об алгоритмах, нам потребуется зафиксировать некоторый язык программирования. Я предлагаю взять за основу упрощённый вариант языка типа Паскаль. При этом в нём нет ограничений на величину используемых чисел, а также мы игнорируем технические моменты типа описания переменных и их типов.

Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.

Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:

print(1);
for i:=1 to 1000000 do print(0)

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

Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.


Многие числа обладают какими-то интересными свойствами. Есть такая "байка" про индийского математика Рамануждана, про которого шутили, что "каждое натуральное число было его личным другом". В одной из историй фигурировало число 1729, вроде бы ничем особым не замечательное. На что индус воскликнул, что это наименьшее натуральное число, которое можно представить в виде суммы двух кубов различными способами: и как 12^3+1^3, и как 10^3+9^3. Я бы не стал пересказывать здесь эту историю, если бы в ней не присутствовал оборот насчёт "наименьшего натурального числа, которое ..." -- про это ещё пойдёт речь в дальнейшем.

Итак, представим себе, что какое-то совершенно огромное число, которое мы даже не можем в принципе позволить себе выписать, обладает каким-то особым свойством, причём является наименьшим из таких чисел. Предположим также, что данное свойство проверяется при помощи алгоритмической процедуры. Тогда можно последовательно перебирать числа n = 1, 2, 3, ... , пока мы не наткнёмся на первое "замечательное" число, обладающее интересующим нас свойством. Процесс нахождения этого числа и его распечатывания может занять миллиарды световых лет, но нас это в данном случае не интересует: важно то, что у этого числа есть совсем короткое описание в виде программы, позволяющее в конечном итоге его найти и распечатать.

Теперь настало время определить ту функцию, о которой далее пойдёт речь. Для каждого числа n, которое мы хотели бы распечатать, существует самая короткая по длине программа на нашем языке, которая это делает. Длина такой программы зависит только от n, то есть является функцией, которую мы далее обозначим через f(n). Именно эта функция (длина самой короткой программы, печатающей число n) и будет невычислимой, что мы далее собираемся доказать.

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

Прежде чем перейти к доказательству, отметим то, что вместо чисел мы могли бы рассматривать любые тексты. Здесь нас интересовал бы способ задать текст наиболее "экономно", то есть написать как можно более короткую инструкцию по его генерации. Фактически, это вопрос о наиболее экономном способе сжатия текста. Но с числами работать удобнее, поэтому мы на них и будем основываться.

Итак, предположим, что функция f(n) вычислима. Тогда существует программа её вычисления, написанная на нашем языке, которую можно оформить в виде процедуры (подпрограммы). Нашей целью является доказательство того, что предположение о существовании такой программы приводит нас к противоречию.

Начнём с того, что на основе имеющейся подпрограммы мы напишем новую программу, на вход которой подаётся какое-то число m, и нас далее интересует наименьшее из чисел, которое нельзя напечатать при помощи программы, длина которой не превышает m символов. Очевидно, что такое число существует: ведь программ ограниченной длины конечное число, и они способны напечатать только конечное количество чисел. А всего их бесконечно много, поэтому существует наименьшее, которое таким способом не напечатать.

Здесь уже у читателя, знакомого с логической проблематикой, должен возникнуть в сознании известный парадокс Берри. Коротко напомним его суть. Некоторыми фразами обычного языка можно задавать числа. Например: "наименьшее трёхзначное число". Этот текст задаёт число 100. Или фраза, сказанная Рамануджаном, прозвучавшая выше, задаёт число 1729. Парадокс состоит в рассмотрении такой фразы:

"наименьшее натуральное число, которое нельзя задать фразой менее чем из двадцати слов".

С одной стороны, фраз из менее чем 20 слов конечное число, поэтому ими можно задать лишь конечную совокупность чисел. Ввиду того, что натуральных чисел бесконечно много, найдутся числа, не задаваемые такими фразами, а среди них какое-то окажется наименьшим. С другой стороны, в рассматриваемой фразе слов меньше 20, и получается, что она именно это число и задаёт. Противоречие!

Сам этот лингвистический парадокс широко известен, ему 100 с лишним лет. Анализировать его в мои планы не входит, и похожие вещи я проделывал с несколькими известными парадоксами.

Итак, пишем программу для процедуры g(m) примерно таким образом:

n:=1;
while f(n)<=m n:=n+1;
g:=n

То есть перебираем все значения n=1,2,3,... , пока не обнаружим самое первое, для которого f(n) > m. Это и будет наименьшее число n, которое не может напечатать программа не более чем из m символов. Таким образом, вычислимость функции f влечёт вычислимость функции g.

Полученный текст программы имеет какую-то определённую длину. Пусть это будет K символов. Допишем к имеющемуся тексту команду:

print(g(K+100))

Ясно, что мы добавили менее 100 символов, и полученный текст имеет длину меньше K+100. С другой стороны, эта программа печатает число g(K+100), то есть наименьшее натуральное число, которое нельзя напечатать при помощи программы длиной не более K+100. Налицо противоречие, и оно означает, что наше предположение о вычислимости функции f(n) было неверным. То есть f невычислима.

В заключение скажем несколько слов о смысле данного результата. Пусть мы хотим узнать, какова наименьшая длина программы, печатающей некоторое достаточно большое число n. Допустим, что прямое распечатывание числа требует 1000 символов. Будет ли это значение наименьшим? Имеется пусть очень большое, но конечное число программ ограниченной длины. Напишем их тексты в рамках мысленного эксперимента, и запустим каждую из программ на своём компьютере. Прошло какое-то время, некоторые из программ остановились. Некоторые из них могли напечатать какие-нибудь числа, но не то, которое нас интересует. Вот какая-то программа из 900 символов, проработав год, напечатала наше число n. Рекорд тем самым побит, то не будет ли он побит далее какой-то более короткой программой? Часть программ мы можем проанализировать, понять принцип их работы, и понять, что они зацикливаются, и по этой причине никогда не остановится. Но вот есть программа из 800 символов, она продолжает работу. Что она делает, мы не понимаем. У нас перед глазами полный её текст, который целиком определяет её дальнейшую "судьбу", но нам она неизвестна. Возможно, эта программа давно уже совершает какие-то малоосмысленные действия, которые ни к чему не ведут. А может так оказаться, что она изо всех сил старается, чтобы за миллиард световых лет напечатать наше число n, почему бы и нет?

Иными словами, мы не располагаем возможностью узнать по данной программе, остановится ли она за конечное время. Если бы мы умели решать эту задачу алгоритмически, то умели бы вычислять и функцию f. То есть в качестве следствия легко получается, что проблема остановки программ алгоритмически неразрешима, что является важным результатом теории алгоритмов. Он, в каком-то смысле, говорит об ограниченной познавательной способности "машинного разума". Заметим, что многие интересуются классическими теоремами Гёделя о неполноте именно по причине того, что из них следует примерно то же самое. Однако часто возражают, что какое нам дело до каких-то искусственных утверждений о недоказуемости некоторых истинных формул? Здесь же, говоря об алгоритмически неразрешимых проблемах, мы имеем дело с более сильными результатами, полученными уже после Гёделя. О чём они говорят? Я бы ответил так: о принципиальной невозможности проникнуть в смысл достаточно сложных текстов.

Оставить комментарий

Популярные посты:

• Архив