Изменения

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

Разрешимые (рекурсивные) языки

Нет изменений в размере, 08:41, 23 декабря 2011
Нет описания правки
'''return''' <tex> 1 </tex>
Теперь рассмотрим вызов <tex> r(r) </tex>.:* Если если <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''if''' выполнится и программа зависнет. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>.;* Если если <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''if''' не выполнится и программа вернет <tex>1</tex>. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
271
правка

Навигация