Материал из Викиконспекты
Основные определения
| Определение: |
| Рекурсивный язык (англ. 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 \ e [/math]
[math]int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits \ 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] |
Источники информации
