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

[falcao]

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

Comments

[falcao]

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

Или вот такой пример, который уже звучал: "наименьшее натуральное число, которое можно представить в виде суммы двух кубов натуральных чисел более чем одним способом" (способы a^3+b^3 и b^3+a^3 считаются одинаковыми). Допустим, Вам сказали бы такую фразу, а Вы не знаете, чему конкретно это число равно. И вообще априори неочевидно, что оно существует. Но никто не мешает начать проверку. Для каждого конкретного числа Вы можете выписать все способы представления, и для чисел от 1 до 1728 убедиться в том, что они или не представляются, или представляются одним способом. А 1729 представляется двумя. Согласны ли Вы с тем, что такое задание фразой более чем "конструктивно"?

Давайте заодно рассмотрим пример явно "неконструктивного" числа. Я говорю: рассмотрим натуральное число n. Под ним я могу понимать что угодно. Никто не мешает с этим числом как-то далее работать - например, рассматривать n+1 или 2n. Но никто не знает, чему это число равно. Вот это пример числа, которое рассматривается, но оно при этом не задано, и нет никакого способа определить, что это за число.

Под выписыванием всех текстов я понимал выписывание текстов менее чем из 20 слов. Эта задача в рамках мысленного эксперимента вполне решается. Можно также представить себе все такие тексты - этого достаточно. Если так, то напротив каждого текста можно написать какое угодно число, и сказать, что это и будет наше правило задания. Например, мне никто не мешает напротив фразы "наименьшее простое число" написать 10. Другое дело, что такое правило будет противоречить "принципу семантической корректности" (я когда-то пояснял, что это значит). Суть парадокса Берри именно в этом: никакое явное правило задания не будет семантически корректно. А без явного правила (пусть даже сформулированного кем-то и как-то неизвестным для нас способом) мы не вправе рассматривать "парадоксальную" фразу, которая будет апеллировать к свойству, которого пока нет.

[roman_rogalyov]

//слово "конструктивность", и полезно было бы понять, какой смысл в это вкладывается. //

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

[kaktus77]

== Под выписыванием всех текстов я понимал выписывание текстов менее чем из 20 слов

Это, конечно, конструктивная процедура. Значит, я Вас неправильно понял.

== Суть парадокса Берри именно в этом: никакое явное правило задания не будет семантически корректно.

А в чём тут парадокс тогда не понял. Вроде, очевидно, что набору произвольных текстов можно приписать числа только семантически случайно.

Парадоксально было бы как паз наличие в такой ситуации какой-либо "семантической корректности" :)