Изменения

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

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

2 байта убрано, 22 март
Проблема остановки
|statement= Проблема остановки неразрешима
|proof= Докажем от противного. Предположим существует такая полностью вычислимая функция <tex>halts(f)</tex>, которая возвращает <tex>true</tex>, если функция <tex>f</tex> остановится когда-либо, и <tex>false</tex>, если функция <tex>f</tex> никогда не остановится.
 
Рассмотрим следующую функцию <tex>g</tex>
<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> остановится, получили противоречие
}}
Анонимный участник

Навигация