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

[falcao]

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

Comments

[lj_frank_bot]

Hello!
LiveJournal categorization system detected that your entry belongs to the following categories: История, Космос, Наука.
If you think that this choice was wrong please reply this comment. Your feedback will help us improve system.
Frank,
LJ Team

[falcao]

Истории тут нет, Космоса тоже нет. Есть Математика.

[lj_frank_bot]

Спасибо, ваш ответ делает нас лучше

[kaktus77]

== о принципиальной невозможности проникнуть в смысл достаточно сложных текстов.

В смысл некоторых искусственных текстов, который в общем-то никого не интересует :)

== чтобы за миллиард световых лет напечатать

Шутка? Световыми годами вообще-то измеряется расстояние, а не время.

[falcao]

Нет, здесь не идёт речь о каких-то заведомо не представляющих интереса текстах - это важное обстоятельство. Тут создана как бы специальная "интрига": есть текст, он довольно короткий, и предположим, что для нас "судьбоносно" то, выдаст ли программа некий результат, который для нас важен. При этом вполне естественно пытаться понять, что происходит. Получается, что уже короткий текст представляет из себя, если можно так выразиться, "личность", то есть нечто, поведение чего (или кого) определяется этим самым "чем" (или "кем"), и не сводится к чему-то более простому. Это ли не Чудо?

Про световые года написал неосознанно - после Вашего замечания самому стало смешно. Пусть тогда это будет что-то типа "стопицот" :)

[kaktus77]

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

Смысл не в тексте, а в деятельности.

[falcao]

Случай, когда у нас есть замысел, и мы потом обращаем его в текст программы, вполне возможен. Но представьте себе такую ситуацию: объявлен какой-то конкурс, я реализую свой замысел, а потом оказывается, что у кого-то он лучше. То есть его программа короче моей. Я до неё не додумался, и при этом она отнюдь не случайна. Почему мы тогда не можем представить себе Сверхразум, который реализовал какой-то недоступный для нашего понимания замысел? Среди кучи вроде бы случайных и бессмысленных программ оказалась одна, которая вовсе не "случайна", а просто сложна для понимания.

Насчёт лозунга о том, что смысл в деятельности: я с ним вполне согласен, но там это всё присутствует. Сложная программа осуществляет некую деятельность, приводящую к успеху. Но мы не можем всё это постичь.

[dims12]

Правильно ли я понимаю, что доказательство не работает, если верно утверждение

Существует такое конечное N, что для любого числа, существует программа короче N, способная напечатать это число.

И при этом f(n) длиннее N

[falcao]

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

[dims12]

Не уверен, ведь тут можно использовать тот же приём.

Возьмём, скажем, короткую программу

для каждого n от 0 до 1000
сгенерировать каждую возможную программу длиной n
запустить её

С одной стороны, она короче 1000 единиц, с другой стороны, делает всё, что делают программы длиной вплоть до 1000 единиц.

[rus4]

"сгенерировать каждую возможную программу длиной n"

это не процедура на нашем языке программирования

[kaktus77]

== известный парадокс Берри.

Парадокс, вроде, тривиально решается.
Сакраментальная фраза, которая меньше 20 слов задаёт не число, а знание о существовании числа. Причём, по этому знанию нельзя построить число (фраза не конструктивна).

Ну а дальше за счёт логической ошибки (отождествлении числа и знания о его существовании) создаётся видимость парадокса.

Наверное, и с вычислимостью какой-то такой трюк, но тут более запутанно :)

[falcao]

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

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

[kaktus77]

==Если считать, что фраза даёт знание о существовании числа, то почему нельзя считать, что она вместе с этим задаёт и число

[falcao]

Вы часто использовали слово "конструктивность", и полезно было бы понять, какой смысл в это вкладывается. Вот, например, число 10^{10^10} "конструктивно"? С одной стороны, вроде бы да - оно вполне однозначно этим выражением задано. С другой стороны, никто из нас досчитать до такого огромного числа не в состоянии. Но здесь везде принимается гипотеза потенциальной осуществимости - надеюсь, это ясно

[fiviol]

Спасибо, интересно!
Мне кажется, однако, что у вас логическая ошибка, когда вы заявляете о невозможности понять смысл работы конкретной программы из 800 символов на основе того, что не существует общего алгоритма понимания смысла произвольной программы.

> Я бы ответил так: о принципиальной невозможности проникнуть в смысл достаточно сложных текстов.
Вполне вероятно, впрочем, что текст вашего поста достаточно сложен, и я просто не проник в его смысл. :)

[falcao]

Здесь приведён некий условный иллюстративный пример, цель которого - "высветить" определённую мысль. С одной стороны понятно, что сложность надо рассматривать на основе массовой проблемы, а не частного случая её решения. Но это с формальной стороны. А с неформальной - мы так не рассуждаем. Было, допустим, пять случаев для рассмотрения какого-то процесса. Из них оказалось два лёгких, один средней трудности, один очень трудный, а последний - вообще непонятный. И так пытались понять, и этак - ничего не вышло. Никаким образом не смогли понять принцип работы программы

[cmt96]

По-моему, нужно уточнение.

Есть определённые задачи - например, дать машину, которая перечисляет доказательства всех "интересных" теорем.

Так вот, математический факт состоит не в том, что это сделать невозможно, а в том, что невозможно математически доказать, что какая-то машина обладает подобным свойством.

В конечном итоге - по-моему, разницы нет, но, мне кажется, есть смысл различать, о чём идёт речь.

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