Изменения

Перейти к: навигация, поиск

Тьюринг-полнота

518 байт добавлено, 20 март
Теорема Геделя о неполноте
{{Теорема
|statement= Любая непротиворечивая формальная система аксиом <tex>T</tex>, способная выражать утверждения о натуральных числах и доказывать простые арифметические факты, неполна {{---}} существуют утверждения о натуральных числах, которые она не может ни доказать, ни опровергнуть.
|proof= Чтобы доказать теорему, можно воспользоваться проблемой остановки машины Тьюринга (доказанной Аланом Тьюрингом в 1936).
{{Теорема
|statement= Для данной машины Тьюринга и входных данных для нее невозможно определить, остановиться ли она когда-либо (запущенная на этих данных) или нет
}}
}}
Анонимный участник

Навигация