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

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

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

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

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

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

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

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

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

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

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

Другими словами, универсальный язык — это язык всех программ и их входных данных, на которых программа возвращает [math]1[/math]. Программа — это набор строк, занумеровав которые, можем получить биекцию между строками и натуральными числами.

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Приведём доказательство от противного. Пусть язык [math]U[/math] разрешим, тогда существует программа [math]u(\langle p, x \rangle) = \begin{cases} 1, \ \langle p, x \rangle \in U \\ 0, \ \langle p, x \rangle \notin U \end{cases} [/math]

[math]\triangleleft[/math]

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

[math]r(x) {:} [/math]
  if [math]u(\langle x, x \rangle) == 1 [/math]
    while (true)
  else
    return 1

Рассмотрим вызов [math] r(r) [/math]:

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

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

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

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