Изменения
Нет описания правки
{{Определение
|definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex> и , а для <tex> \forall w \notin L: p(w) = 0</tex>.
}}
=Примеры=
==Пример разрешимого множества==
{{Утверждение
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую наш язык:
<tex>p(i)</tex>
'''if''' (остаток от деления i на 2 = 0)
'''return''' 1
'''else'''
'''return''' 0
Заметим, что программа нигде не может зависнуть.
}}
==Пример неразрешимого множества==
{{Определение
|definition=Язык <tex> U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex> называется '''универсальным'''.
}}
{{Утверждение
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Докажем от противного. </br>
Пусть язык <tex> U </tex> разрешим. </br>
Тогда существует такая программа <tex> u </tex>, что
<tex>p(i)</tex>
'''if''' (остаток от деления i на 2 = 0)
'''return''' 1
'''else'''
'''return''' 0
Программа нигде не может зависнуть и таким образом разрешает наш язык.
}}
