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

Определение:

Язык [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 [math] i \equiv 0 \ (mod \ 2) [/math] return [math] 1 [/math] else return [math] 0 [/math] Заметим, что программа нигде не может зависнуть.

[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 [math] u(\langle x, x \rangle) = 1 [/math] while [math] true [/math] else return [math] 1 [/math] Теперь рассмотрим вызов [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]

Литература

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999