Изменения

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

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

589 байт добавлено, 20 март
Теорема Геделя о неполноте
|statement= Для данной машины Тьюринга и входных данных для нее невозможно определить, остановиться ли она когда-либо (запущенная на этих данных) или нет
}}
# Предположим, что система <tex>T</tex> еще и корректна (доказывает только истинные условия).
# Предположим, что система <tex>T</tex> полна, т.е. доказывает или опровергает любое утверждение.
# Сформулируем и запишем на языке арифметики утверждение <tex>O</tex> = "машина Тьюринга <tex>M</tex> точно остановится, если запустить ее с данными <tex>D</tex>"
}}
Анонимный участник

Навигация