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

[gul_kiev]

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

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

Comments

[iaroshenko]

Первая часть в целом верная (хотя я никогда не слышал, чтобы УМТ называли просто "интерпретатором

[gul_kiev]

Так...
То есть, не существует алгоритма, который способен ответить на вопрос останова про любой другой алгоритм, но при этом не существует алгоритма, про который невозможно сказать, остановится он или нет - правильно?

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

[iaroshenko]

Здесь скрываются два разных понятия

[gul_kiev]

Да, я имел ввиду, конечно, 2), т.е. утверждения, которые принципиально нельзя ни доказать, ни опровергнуть, для которых ни само утверждение, ни его отрицание, не следуют из аксиом и не противоречат им.

И да, я о том и говорил, что Пенроуз (если я его правильно понял) считает, что человек из недоказуемости утверждения о том, остановится ли алгоритм, делает вывод, что этот алгоритм не остановится, а машина такой вывод сделать не сможет, т.к. формально этот вывод из аксиом не следует.

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

То есть, в моих рассуждениях всё правильно?
И гипотеза Гольбаха не может оказаться гёделевским утверждением лишь в том смысле, что мы её в таком случае будем считать доказанной (ведь это будет значить, что привести пример такого числа невозможно), даже если отсутствие такого числа не будет следовать из аксиом Пеано - так?

[iaroshenko]

Вы оперируете понятием "гёделевский алгоритм", которое я затрудняюсь строго определить. Поэтому трудно сказать, правильны ли рассуждения.

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

Гипотеза Гольдбаха не доказана лишь в смысле 1). Можем ли мы вывести ее из системы аксиом - зависит от системы аксиом.

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

[gul_kiev]

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

[iaroshenko]

>Когда говорим про аксиоматику системы натуральных чисел без явного указания системы аксиом, подразумеваем аксиоматику Пеано

[gul_kiev]

> Когда я говорю, что что-то истинно в математическом смысле (или как вы говорите, "на самом деле"), я имею в виду консенсус математиков о том, что это утверждение доказано

[iaroshenko]

Я в третий раз отсылаю вас к проекту Володарского и к причинам, по которым он начал этот проект.

Консенсус математиков никогда не считал, что пятиугольников 8 или 15, он считает, что их по крайней мере 15.

Если вы отрицаете апелляцию к авторитетам, то для вас и большая теорема Ферма, и гипотеза Пуанкаре остаются недоказанными.

Edit: прошу прощения, это моя вина. По ошибке я трижды назвал фамилию Володарский. Должно быть: Воеводский.
https://posic.livejournal.com/613891.html
http://philomatica.org/2017/10/%D0%B2%D0%BB%D0%B0%D0%B4%D0%B8%D0%BC%D0%B8%D1%80-%D0%B2%D0%BE%D0%B5%D0%B2%D0%BE%D0%B4%D1%81%D0%BA%D0%B8%D0%B9-1966-2017/

[gul_kiev]

> Если вы отрицаете апелляцию к авторитетам, то для вас и большая теорема Ферма, и гипотеза Пуанкаре остаются недоказанными.

Нет, одно из другого не следует.
Из того, что я по разным причинам не имею возможности у себя на чердаке провести, скажем, эксперимент Майкельсона-Морли или, тем более, зарегистрировать гравитационные волны, вовсе не следует, что я считаю, что критерий истины в физике - консенсус физиков, или что эти эксперименты невоспроизводимы. Нет, критерий истины - воспроизводимость эксперимента и проверяемость теории. В этом основное отличие науки от религии.

Лично перепроверять все научные знания, доказательства и эксперименты слишком накладно и для человека нереально, поэтому мы доверяем это другим людям. Но доверять верификацию и делегировать установление истины - совсем не одно и то же.

Истинность или ложность гипотезы Пуанкаре или ABC-гипотезы не зависит от того, принято ли доказательство консенсусом математиков или не принято.

[gul_kiev]

Проект Воеводского - спасибо, буду смотреть.

[gul_kiev]

Похоже, тут смешались два по сути разных значения слова "доказательство" и именно из-за этой путаницы (поочерёдного применения одного или второго смысла в последовательном рассуждении) и возникли странные последствия вроде неалгоритмизуемости сознания

[proshka_tjubik]

"Если в аксиоматической системе S не выводится ни утверждение A, ни утверждение "не A", то мы можем расширить систему S, добавив в неё утверждение A или добавив в неё утверждение "не A", и получим две разных системы аксиом P и P', каждая из которых непротиворечива"
И что получим в итоге?
Если расширяем S утверждениями А или неА, то получаем непротиворечивые высказывания о условиях существования или несуществования объекта высказывания А.
Не так?

[gul_kiev]

Да.
Например, в евклидовой геометрии и в геометрии Лобачевского существует прямая, параллельная данной, проходящая через точку, не лежащую на этой прямой (в геометрии Лобачевского таких прямых бесконечно много).
А в сферической геометрии таких прямых не существует.
Это и есть разные формальные системы, отличающиеся аксиомой - в одной из этих систем приняли A, а в другой - "не A", причём A - это как раз таки утверждение о существовании некого объекта.

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

[proshka_tjubik]

А у меня - не так.
Геометрия Лобачевского не отменила известную теорему, а всего лишь в новой расширенной системе S предложила решение.
Неважно, что геометрия Евклида вырожденный случай геометрии Лобачевского - опровержения нет.
В гипотезе Гольдбаха мы тоже можем многое ввести и, при желании, можем доказать или опровергнуть формально, но нас интересует доказательство в определённой системе координат, которая постулируется натуральным и простым числом.

[gul_kiev]

Давайте на примере диофантовых уравнений