Изменения

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

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

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

Навигация