Изменения
→Теорема Хайтина о неполноте
}}
==Теорема Хайтина Применение=====Альтернативное доказательство теоремы Гёделя о неполноте===[http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%B9%D1%82%D0%B8%D0%BD,_%D0%93%D1%80%D0%B5%D0%B3%D0%BE%D1%80%D0%B8 Г. Хайтин] заметил следующее:{{Утверждение|statement= В данной фиксированной системе вывода существует недоказуемое утверждение вида <tex>KS(x) \geqslant n</tex>|proof=Выпишем множество пар <tex>\{(x,n) |\ </tex> утверждение <tex>KS(x) \geqslant n</tex> доказуемо <tex>\}</tex>. Возможны два варианта:* Все <tex>n \leqslant n_0</tex>. Это означает, что для всех строк будет доказуемо только <tex>KS(x) \geqslant n_0</tex>. Но т.к. мы знаем, что <tex>KS(x)</tex> неограничена, то существуют истинные, но недоказуемые утверждения.* В этом множестве встречаются сколь угодно большие <tex>n</tex>, т.е. есть бесконечная последовательность <tex>(x_i, n_i)</tex>, в которой <tex>n_{i+1} > n_i</tex>. Заметим, что эта последовательность задает график какой-то функции. А если график функции перечислим, то сама функция является вычислимой. Также заметим, что всегда выполняется условие <tex>KS(x_i) \geqslant n_i</tex>, т.е. эта вычислимая функция является нижней оценкой на <tex>KS(x)</tex>, а мы знаем, что такие функции обязаны быть ограниченными. Противоречие.}}Заметим, что во всех множествах пар все <tex>n</tex> ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида <tex>KS(x) \geqslant n</tex>
== Источники ==
