Изменения

|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> никогда не остановится, получили противоречие

}}