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

[gul_kiev]

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

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

Comments

[iaroshenko]

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

Здесь что-то не в порядке, но чтобы сформулировать точно, нужно понять изначальную интенцию

>при помощи алгоритма последовательно выписать все алгоритмы

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

>для этого нужно выписать алгоритмы, останавливающийся на любых входных данных, а для них такой трюк уже не проходит

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

[gul_kiev]

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

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

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

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

> Если вы можете перенумеровать все алгоритмы и добавить к ним пустой вход, точно так же вы можете перенумеровать все алгоритмы со всеми возможными вариантами - все равно получится счетное эффективно перечислимое множество

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

[iaroshenko]

теперь понял