Про Гёделя, Пенроуза и вычислимость

[gul_kiev]

Ещё раз про вычислимость, теорему Гёделя о неполноте, алгоритмизуемость человеческого сознания и Роджера Пенроуза, получившего в этом году Нобелевку.

Почему это интересно?
С одной стороны это одна из наиболее удивительных и неожиданных теорем математики - о том, что (если опустить детали) в любой математической системе найдутся утверждения, которые

Comments

[proshka_tjubik]

"Никакими геометрическими построениями мы не сможем на числовой прямой построить невычислимую точку. " - можем.

[gul_kiev]

Пруф?

[proshka_tjubik]

Под вычислимостью что понимаете, алгоритм вычисления?
Если так, то невычислимых точек не существует.

[gul_kiev]

> Под вычислимостью что понимаете, алгоритм вычисления?

Не только я понимаю, это устоявшийся математический термин.

> Если так, то невычислимых точек не существует.

Невычислимые числа существуют, а соответствующие им точки на числовой прямой не существуют?
Вы не находите это странным?

[proshka_tjubik]

Если невычислимых точек не существует, то не существует и невычислимых чисел.
Предположим, существует невычислимое число N на числовой оси. Невычислимость N означает, что пределы любой бесконечной равномерно сходящейся дроби, при приближении снизу, не приближаются к N и всегда остаётся отрезок между пределом любой дроби и N, который не содержит предела любой дроби. Т.е. N больше предела любой бесконечной дроби. И N , в таком случае, бесконечно большое число на числовой оси.
Не так?

[livelight]

> бесконечной равномерно сходящейся дроби

Дык, а как вы будете строить эту самую дробь, которая сойдётся ровно к числу N? Чтобы рассказать нам, как вы её строите, за конечное время, вам придётся в общем случае стать тем самым идеальным архиватором, который я упомянул выше, а Рэндал - тут: https://xkcd.com/1381/

[proshka_tjubik]

Я ждал этого вопроса. Очевидно, что вычислить неизвестное число нельзя. Поэтому, число должно быть задано каким-либо выражением. Например, число Пи равно отношению длины окружности к диаметру. Как только число задано неким утверждением, оно становится вычислимым.
Время вычисления не рассматривается в математике, если только вопрос не стоит о вычислительном алгоритме для машины. В этом случае время вычисления определено точностью вычисления.

[livelight]

Утверждение - это конечный тест в конечном алфавите. Их не более чем счетное число. А действительных чисел - континуум.

[gul_kiev]

И мало того, существуют определимые (definable), но невычислимые числа.
Алгоритм, который выводит число с любой заданной точностью - не единственный способ определить число.

[gul_kiev]

> Если невычислимых точек не существует, то не существует и невычислимых чисел.

Действительных чисел континуум, а вычислимых счётное множество. Как же в таком случае могут не существовать невычислимые числа?

> Невычислимость N означает, что пределы любой бесконечной равномерно сходящейся дроби
> при приближении снизу, не приближаются к N и всегда остаётся отрезок между пределом любой дроби и N, который не содержит предела любой дроби. Т.е. N больше предела любой бесконечной дроби.

Что такое "предел дроби"? Что такое "равномерно сходящаяся дробь"?
Примените ваше рассуждение к последовательности рациональных чисел, сходящейся к иррациональному числу.

[livelight]

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

[gul_kiev]

> всегда остаётся отрезок между пределом любой дроби и N, который не содержит предела любой дроби

всё равно ниасилил

[livelight]

Это, видимо, комментатор отождествил расходящиеся (или сходящиеся не туда, куда хотелось) последовательности с бесконечно большими :)

[proshka_tjubik]

" Действительных чисел континуум, а вычислимых счётное множество. Как же в таком случае могут не существовать невычислимые числа?"
Любое действительное число можно приблизить как угодно точно бесконечной дробью, следовательно, существует алгоритм вычисления и любое действительное число вычислимо. Впрочем, можете попробовать привести пример невычислимого действительного числа.
"Что такое "предел дроби"? Что такое "равномерно сходящаяся дробь"?"
Я полагал, что понятие предела и равномерной сходимости понятно, хотя признаю, что экспромтом не придерживался кондово-посконной точности в изложении.
"Примените ваше рассуждение к последовательности рациональных чисел, сходящейся к иррациональному числу."
Действительные числа приближаются бесконечной дробью. Рациональное число либо конечная дробь, либо периодическая. Можно приближать действительное число и рациональными дробями, но в этом случае следует говорить о последовательности дробей, сходящейся к действительному числу.

[gul_kiev]

Вы плаваете в базовых вопросах. Если вам несмотря на это интересно общаться на эти темы, пожалуйста, смените тон беседы, и вместо утверждений (которые у вас, зачастую, получаются нелепыми) задавайте вопросы.

Пост изначально discussable и несколько провокационно ставит под сомнение некоторые устоявшиеся в математике положения, но всё-таки не на уровне "Любое действительное число можно приблизить как угодно точно бесконечной дробью, следовательно, существует алгоритм вычисления и любое действительное число вычислимо".

Пример невычислимого числа приведен в конце поста.
Или посмотрите константу Хайтина. Или последовательность Шпекера.

[proshka_tjubik]

Посмотрю.