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

[gul_kiev]

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

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

Comments

[livelight]

Первая часть поста - это изложение размышлений avva? Или он пересказывал Пенроуза

[gul_kiev]

> Первая часть поста - это изложение размышлений avva? Или он пересказывал Пенроуза

[livelight]

> мы предположили, что алгоритм W находит циклы в тех, и только тех алгоритмах, в которых их находит и наше сознание

[livelight]

Ну а если аксиоматически положить, не что W эквивалентен нашему сознанию сознанию человека A, а что он всего лишь умеет обнаруживать циклы в тех и только тех алгоритмах (точнее, в их записи в некой форме -- ибо формы записи бывают разные, с чего я и начал), в каких сможет обнаружить цикл человек А -- то мы всего лишь обнаружим, что человек A, глядя на описание этого алгоритма, снятого с него самого, и записанного в той форме, с которой мы договорились работать, и без дополнительной информации ("чувак, это мы написали тот самый алгоритм, который зависнет!") охренеет и не сможет найти в нём цикл. Точно так же, как он не может доказать Проблему Гольдбаха, например.

[proshka_tjubik]

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

[gul_kiev]

Пруф?

[proshka_tjubik]

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

[gul_kiev]

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

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

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

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

[iaroshenko]

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

[gul_kiev]

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

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

[iaroshenko]

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

[gul_kiev]

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

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

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

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

[iaroshenko]

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

[gul_kiev]

> Здесь что-то не в порядке

[iaroshenko]

теперь понял