Неразрешимая проблема Тьюринга. (5 стр)

=A=L=X=
> А, понял что ты имеешь ввиду - чтобы анализатор конструировал сам себя исходя
> из числа N на лету - и таким образом получить решение проблем века прямо на
> блюдечке. Нет, известно лишь что он есть и все.
А что толку что он есть? Теорема говорит, что мы никак не можем узнать. Т.е. мы не можем создать алгоритма (машину тьюринга) которая бы узнавала, остановится ли N или нет, т.е., в том числе, и что мы не можем построить такой анализатор по заданному произвольному N.
То что ответ есть, т.е. то что машина либо остановится либо нет и так очевидно (в рамках конструктивной математики). То что одна из дающих рандомные ответы машин угадает - тоже в общем очевидно, но мы никак не сможем определить какая именно, т.к. общего алгоритма у нас опять-таки нет. Для маленьких N мы можем подобрать перебором (надеясь что при маленьких N не встретиться какой-нибудь теоремы Ферма), дальше мы построить его не сможем.

kipar

Да, верно.
Это вообще сносит крышу.
Построим вопрос немного по другому - существует ли алгоритм для произвольного N выдающий правильный ответ?
Ответ - да.
Доказательство: т.к. в силу очевидности как ты и сказал - любой непротиворечивый конечный алгоритм или завершится или нет - то строится функция "все ответы", которая возвращает список функций - из 2^N элементов для заданного N перечисляющая все функции вышеописанным мною методом - путём перебора. Алгоритм "все ответы" конечен и тьюрингов как две копейки.
Известно что среди ответов будет верная функция!
Но мы не знаем - какая!
Это незнание не позволяет нам создать "диагонализатор", следовательно для любого N мы знаем что функция существует. Но никаких намёков как её выбрать - поэтому это просто ничего не даёт.
Но блин формально мы знаем что функция есть! =)))) Жесть прямо, да.

=A=L=X=
> Построим вопрос немного по другому - существует ли алгоритм для произвольного N выдающий правильный ответ?
Не для "произвольного" N, а для каждого конечного N.

Аналогия тут простейшая.
Для каждого конечного N существует хорошо определенное число \(x_i = i\). Однако при стремлении N к бесконечности этот ряд предела не имеет.
Также и с алгоритмом определения останова: для каждого конкретного N алгоритм существует, однако "предела" нет.

}:+()___ [Smile]
> Не для "произвольного" N, а для каждого конечного N.

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

}:+()___ [Smile]

Но вообще мы одно и то же говорим другими словами.
Можно сказать иначе - полностью универсальный алгоритм сабжа нельзя записать конечным числом знаков => его не существует как машины тьюринга.

=A=L=X=
> В математике насколько я помню если ты не можешь предьявит такое конкретное N для которого что то перестаёт работать, то тогда и говорится "для любого N", что впрочем и означает что для любого конкретного N.
Тут есть тонкость. Если нечто, единое и неделимое, работает для любого конкретного N, то можно говорить "для любого N". Однако, в данном случае единого "нечта" не существует, есть только независимый объект на каждое N.

Вообще, более корректно будет говорить по другому. Обозначим через \(T[ N ]\) множество машин Тьюринга, решающих проблему останова для алгоритмов длины N. Очевидно, что \(T[ N+1 ]\subset T[ N ]\). И вот тут, как раз, предел при \(N\to\infty\) существует и равен пустому множеству. Т. е. абсолютно явно "не существует машин Тьюринга, решающих проблему останова".