Разрешимые (рекурсивные) языки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры разрешимых множества)
Строка 39: Строка 39:
 
}}
 
}}
  
== Примеры разрешимых множества ==
+
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=

Версия 15:48, 9 января 2015

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

Определение:
Рекурсивный язык (англ. 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
  • Википедия — Рекурсивный язык
  • Методические указания к курсу ”Сложность вычислений” Гамова А.Н.