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

Материал из Викиконспекты
Версия от 01:38, 10 января 2015; 95.54.62.216 (обсуждение) (Основные определения)
Перейти к: навигация, поиск

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

Определение:
Рекурсивный язык (англ. recursive language) [math]L[/math] — язык, для которого существует программа [math]p(w) = \begin{cases} 1, \forall w \in L\\ 0, \forall 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]\to[/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]


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

Для чисел [math]e, \pi[/math] существуют различные техники нахождения их точного представления, одна их которых описана в статье «A Spigot Algorithm for the Digits of Pi». Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon), которые создали свой алгоритм для нахождения цифр числа [math]\pi[/math] в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, и предназначался тот алгоритм для нахождения цифр числа [math]e[/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 = 0;; ++i)  
  if (getDigit([math]e[/math], i) > getDigit([math]r[/math], i))
    return 1
  if (getDigit([math]e[/math], i) < getDigit([math]r[/math], i))
    return 0
Так как число 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]
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].
Из предположения о разрешимости универсального языка мы пришли к противоречию.
[math]\triangleleft[/math]

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