Изменения
→Теорема Геделя о неполноте
Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. Brainfuck, Spoon, Malbolge, Whitespace).
==Теорема Геделя о неполнотеПроблема остановки==Чтобы доказать теорему, можно воспользоваться проблемой остановки машины Тьюринга (доказанной Аланом Тьюрингом в 1936).
{{Определение
|definition= Для данной машины Тьюринга и входных данных для нее \определить, остановится ли она когда-либо (запущенная на этих данных) или нет.
}}
{{Теорема
|statement= Проблема остановки неразрешима
|proof=Докажем от противного. Предположим существует такая полностью вычислимая функция <tex>halts(f)</tex>, которая возвращает <tex>true</tex>, если функция <tex>f останавливается</tex> остановится когда-либо, и <tex>false</tex>, если функция <tex>f </tex> никогда не остановится. Рассмотрим следующую функцию <tex>g</tex> '''void''' g(): '''if''' halts(g): '''for'''(;;)<tex>halts(g)</tex> должна возвращать либо <tex>true</tex>, либо <tex>false</tex>.* Если <tex>halts(g)</tex> вернула <tex>true</tex>, то <tex>g</tex> никогда не остановится, получили противоречие* Если <tex>halts(g)</tex> вернула <tex>false</tex>, то </tex>g</tex> остановится, получили противоречие
}}
==Теорема Геделя о неполноте==
Чтобы доказать теорему, можно воспользоваться проблемой остановки машины Тьюринга.
{{Теорема
|statement= Любая непротиворечивая формальная система аксиом <tex>T</tex>, способная выражать утверждения о натуральных числах и доказывать простые арифметические факты, неполна {{---}} существуют утверждения о натуральных числах, которые она не может ни доказать, ни опровергнуть.
# Поскольку система <tex>T</tex> доказывает только истинные факты, мы фактически решили проблему остановки.
Это очень простой способ доказательства теоремы Геделя о неполноте, но при этом он требует корректности <tex>T</tex> (тем не менее обычные системы аксиом арифметики всегда корректны).
}}
==См. также==
