Изменения
→Теорема Геделя о неполноте
==Теорема Геделя о неполноте==
Чтобы доказать теорему, можно воспользоваться проблемой остановки машины Тьюринга (доказанной Аланом Тьюрингом в 1936).
{{Определение
|definition= Для данной машины Тьюринга и входных данных для нее \определить, остановится ли она когда-либо (запущенная на этих данных) или нет.
}}
{{Теорема
|statement= Для данной машины Тьюринга Проблема остановки неразрешима|proof=Докажем от противного. Предположим существует такая полностью вычислимая функция halts(f), которая возвращает true, если функция f останавливается, и входных данных для нее невозможно определитьfalse, если функция f никогда не остановится ли она когда-либо (запущенная на этих данных) или нет.
}}
{{Теорема
# Так как система <tex>T</tex> полна, рано или поздно мы найдем опровержение или доказательство утверждения <tex>O</tex>
# Поскольку система <tex>T</tex> доказывает только истинные факты, мы фактически решили проблему остановки.
Это очень простой способ доказательства теоремы Геделя о неполноте, но при этом он требует корректности <tex>T</tex> (тем не менее обычные системы аксиом арифметики всегда корректны). }}
==См. также==
