Материал из Викиконспекты
Основные определения
| Определение: |
| Рекурсивный язык (англ. 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] |
Примеры неразрешимых множества
| Лемма: |
Универсальный язык неразрешим. |
| Доказательство: |
| [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] |
Источники информации
