Изменения
→Проблема остановки
==Проблема остановки==
{{Определение
|definition= Проблема остановки {{---}} определить, остановится ли данная машина проблема определения факта остановки данной машины Тьюринга на данных входных данных когда-либо (закончит выполнение или нет).
}}
{{Теорема
# Поскольку система <tex>T</tex> доказывает только истинные факты, мы фактически решили проблему остановки.
Это очень простой способ доказательства теоремы Геделя о неполноте, но при этом он требует корректности <tex>T</tex> (тем не менее обычные системы аксиом арифметики всегда корректны).
"Перекроим" доказательство, используя только непротиворечивость: если доказываемое утверждение оказалось ложным, мы все ещё решили проблему остановки.
}}
