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

[falcao]

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

Comments

[bokhonov]

Смысл текста - феномен не сводимый полностью к формальным конструкциям.
Поэтому интересно понятие - математический смысл.
Вот читал, что Рассел выдал фразу, типа - математика это такая наука, где мы не знаем, о чём говорим.
:)

Нечто вроде коана в дзене.
Над этим хорошо медитировать в буддийском стиле.
На предмет - из чего сделана математика.

Световой год это расстояние, а не временной период, но как аллегория вполне применима.

<<<С одной стороны, фраз из менее чем 20 слов конечное число, поэтому ими можно задать лишь конечную совокупность чисел

[rasterjasha]

а Андерсен понимал тщетность ;)

[109]

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

Интересно было бы параметризовать это утверждение, например "наименьшее натуральное число, которое нельзя задать фразой менее чем из N слов", и попытаться понять, при каком N возникает парадокс (ни при N = 1, ни при N = 2 парадокса очевидно нет, по крайней мере в русском языке)

[falcao]

Здесь N должно быть таково, чтобы сама фраза подходила, то есть содержала менее N слов. Поэтому вместо 20 (я брал "круглое" значение) можно было взять 13.

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

Можно даже так не "хитрить", а говорить о фразах не более чем из одного предложения.

[mathreader]

Прошу прощения, а что понимается под фразой "f(n) определена"? Мне казалось, что функция определена, если задана процедура (пусть бесконечной длины) для ее вычисления. Например, объединение алгоритмов все возрастающих длин. Но в данном случае все выглядит, как не определенность самой функции f(n). Т.е. при попытке установить, чему равно f(20), возникает парадокс Берри. Я не прав?

[cmt96]

2*2 = 2+2 = 4. Эти равенства кажутся особенными: где ещё + и * так легко меняются местами