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

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

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

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

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

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

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

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

Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется вычислимой (англ. computable), если существует программа [math]p : \forall n \in D(f) \Rightarrow p(n) = f(n), \forall n \notin D(f) \Rightarrow p(n) = \bot [/math].

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

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

Воспользуемся известной формулой для вычисления числа e [math] = \sum \limits_{n=0}^{\infty} 1/n! [/math], с помощью которой e может быть вычислено с произвольной точностью. Приведем программу, разрешающую данный вопрос: [math]p(r): [/math] [math]int[] \ eDigits = getDigits(e) \ // \ array \ of \ digits \ in \ e [/math] [math]int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits \ in \ r [/math] [math] \mathrm{for}[/math] (i = 0 to eDigits.length()) [math] \mathrm{if} [/math] (rDigits[i] > eDigits[i]) [math] \mathrm{return} \ 0 [/math] [math] \mathrm{if} [/math] (rDigits[i] < eDigits[i]) [math] \mathrm{return} \ 1 [/math] Так как число e иррационально, то ответ будет найден.

[math]\triangleleft[/math]

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

Лемма:

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

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

[math]\triangleright[/math]

Приведём доказательство от противного. Пусть язык [math]U[/math] разрешим, тогда существует программа [math] u [/math] : [math] \forall \langle p, x \rangle \in U \Rightarrow u(\langle p, x \rangle) = 1[/math], [math] \forall \langle p, x \rangle \notin U \Rightarrow u(\langle p, x \rangle) = 0[/math]. Составим следующую программу: [math]r(x):[/math] [math] \mathrm{if} \ u(\langle x, x \rangle) == 1 [/math] [math]\mathrm{while} \ true [/math] [math] \mathrm{else} [/math] [math]\mathrm{return} \ 1 [/math] Рассмотрим вызов [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]. Из предположения о разрешимости универсального языка мы пришли к противоречию.

[math]\triangleleft[/math]

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

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