Изменения
Нет описания правки
}}
==Пример разрешимого множества==
{{Утверждение
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i)</tex>
'''if''' остаток от деления <tex> i на \equiv 0 \ (mod \ 2 = 0) </tex> '''return''' <tex> 1</tex>
'''else'''
'''return''' <tex> 0</tex>
Заметим, что программа нигде не может зависнуть.
}}
<tex>r(x)</tex>
'''if''' <tex> u(<\langle x, x>\rangle) = 1</tex> '''while''' <tex> true</tex>
'''else'''
'''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>.
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
}}
== Литература ==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
