Материал из Викиконспекты
| Определение: |
| Язык [math]L[/math] называется разрешимым (рекурсивным), если существует такая программа [math] p [/math], что [math] \forall w \in L: p(w) = 1[/math], а для [math] \forall w \notin L: p(w) = 0[/math]. |
Примеры
Пример разрешимого множества
| Утверждение: |
Язык чётных чисел разрешим. |
| [math]\triangleright[/math] |
|
Приведём программу, разрешающую язык чётных чисел:
[math]p(i)[/math]
if остаток от деления i на 2 = 0
return 1
else
return 0
Заметим, что программа нигде не может зависнуть. |
| [math]\triangleleft[/math] |
Пример неразрешимого множества
| Определение: |
| Язык [math]\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} [/math] называется универсальным. |
| Утверждение: |
Универсальный язык неразрешим. |
| [math]\triangleright[/math] |
|
Доказательство от противного.
Пусть язык [math] U [/math] разрешим.
Тогда существует такая программа [math] u [/math], что [math] \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = 1[/math], а для [math] \forall \langle p, x \rangle \notin U: u(\langle p, x \rangle) = 0[/math].
Составим следующую программу:
[math]r(x)[/math]
if u(<x, x>) = 1
while true
else
return 1
Теперь рассмотрим вызов [math] r(r) [/math].
- Если [math] u(\langle r, r \rangle) = 1 [/math], то условие if выполнится и вызов зациклится. Но, так как программа [math] u [/math] разрешает универсальный язык, [math] u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1[/math].
- Если [math] u(\langle r, r \rangle) = 0 [/math], то условие if не выполнится и вызов вернёт [math]1[/math]. Но, так как программа [math] u [/math] разрешает универсальный язык, [math] u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1[/math].
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию. |
| [math]\triangleleft[/math] |
