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

Основные определения

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

Рекурсивный язык (англ. recursive language) $L$ — язык, для которого существует программа $p(w) = \begin{cases} 1, \ w \in L \\ 0, \ w \notin L \end{cases}$

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

Язык $L$ называется разрешимым, если существует такая вычислимая функция $f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1$.

Если мы рассматриваем язык $L$ как проблему, то проблема называется разрешимой, если язык $L$ рекурсивный. В противном случае проблема называется неразрешимой. Но часто данные понятия просто отождествляются.

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

Класс всех разрешимых (рекурсивных) языков (англ. Class of decidable (recursive) languages) часто обозначается буквой $\mathrm{R}$.

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

Универсальный язык (англ. universal language) $\ U = \{\langle p, x \rangle \ |\ p(x) = 1\}$.

Другими словами, универсальный язык — это язык всех таких пар "программа и её вход", что программа на входе возвращает $1$.

Рассмотрим данное определение более детально, для чего докажем вспомогательную лемму:

Лемма:

Существует биекция между строками и натуральными числами.

Доказательство:

$\triangleright$

Приведем пример такой биекции: занумеруем подряд все строки длины $1$, затем все строки длины $2$ и так далее — нумерация названий столбцов в $Excel$, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.

$\triangleleft$

Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:

$2^{\mathtt{code}} \cdot 3^{\mathtt{input}}$, где $\mathtt{code}, \ \mathtt{input}$ — есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.

Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом $\Sigma$.

Примеры разрешимых множеств

Утверждение:

Язык чётных чисел разрешим.

$\triangleright$

Приведём программу, разрешающую язык чётных чисел: $p(i) {:}$ if $i \ \bmod \ 2 == 0$ return 1 else return 0 Заметим, что программа нигде не может зависнуть.

$\triangleleft$

Утверждение:

Множество всех рациональных чисел, меньших числа $e$ (основания натуральных логарифмов) или $\pi$, разрешимо.

$\triangleright$

Для чисел $e, \ \pi$ существуют различные техники нахождения их точного представления, одна их которых описана в статье, таким образом, возможно получить необходимый знак чисел $e, \ \pi$ за конечное время. Десятичное представление рационального числа $r$ может быть получено с любой точностью. Приведем программу, разрешающую данную проблему для числа $e$: $p(r) {:}$ if ($r$ < 2) return 1 if ($r$ > 3) return 0 for (i = 1 .. $\infty$) if (getDigit($e$, i) > getDigit($r$, i)) // getDigit — функция, которая получает i-ую цифру вещественной части переданного числа return 1 if (getDigit($e$, i) < getDigit($r$, i)) return 0 Так как число $e$ иррационально, то ответ будет найден за конечное время.

$\triangleleft$

Утверждение:

Множество тех $n$, для которых в числе $\pi$ есть не менее $n$ девяток подряд, разрешимо.

$\triangleright$

Предположим, что в числе $\pi$ встречается $k$ девяток подряд, тогда, логично, что встречается и любое число девяток меньших $k$. Рассмотрим все программы семейства: $p_0(i) {:}$ return 1 $p_1(i) {:}$ if $i \lt 1$ return 1 else return 0 $p_2(i) {:}$ if $i \lt 2$ return 1 else return 0 $\dots$ $p_k(i) {:}$ if $i \lt k$ return 1 else return 0 $\dots$ По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.

$\triangleleft$

Примеры неразрешимых множеств

Утверждение:

Универсальный язык неразрешим.

Доказательство

Приведём доказательство от противного.

Пусть язык $U$ разрешим, тогда существует программа

$u(\langle p, x \rangle) = \begin{cases} 1, \ \langle p, x \rangle \in U \\ 0, \ \langle p, x \rangle \notin U \end{cases}$

Составим следующую программу:

$r(x) {:}$
  if $u(\langle x, x \rangle) == 1$
    while true
  else
    return 1

Рассмотрим вызов $r(r)$:

• Eсли $u(\langle r, r \rangle) = 1$, то условие $\mathrm{if}$ выполнится и программа зависнет, но, так как программа $u$ разрешает универсальный язык, $u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1$;
• Eсли $u(\langle r, r \rangle) = 0$, то условие $\mathrm{if}$ не выполнится и программа вернет $1$, но, так как программа $u$ разрешает универсальный язык, $u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1$.

Из предположения о разрешимости универсального языка мы пришли к противоречию.

Альтернативное доказательство с использованием теоремы о рекурсии

По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию $\mathrm{getSrc()}$, которая вернёт строку — исходный код программы. Допустим, что он разрешим. Тогда напишем такую программу:

 p(x):
   if u(getSrc(), x)
     while true
   else
     return 1

Если $u(p, x) = 1$, тогда программа $p$ на входе $x$ должна вернуть $1$, но по условию $if$ она зависает, а следовательно, не принадлежит универсальному языку.

Если же $u(p, x) \neq 1$, то мы пойдём во вторую ветку условного оператора и вернём $1$, значит, пара $\langle p, x \rangle$ принадлежит универсальному языку, но $u(p, x) \neq 1$, значит, пара не принадлежит. Опять получили противоречие.

Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка

Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка $L=\{p|p(\epsilon)=\perp\}$.

Лемма:

Язык $L=\{p|p(\epsilon)=\perp\}$ неразрешим.

Доказательство:

$\triangleright$

Предположим обратное, тогда существует программа $r$ разрещающая $L$. Рассмотрим следущую программу: p(x) if r(p) return 1 while true Пусть $p(\epsilon)=\perp$. Тогда условие $r(p)$ выполняется и $p(\epsilon)=1$. Противоречие. Если $p(\epsilon) \ne \perp$, то $r(p)$ не выполняется и $p(\epsilon)=\perp$. Противоречие.

$\triangleleft$

Источники информации

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
• Wikipedia — Recursive language
• Википедия — Рекурсивный язык