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

2015-01-07T13:21:51Z

178.70.4.202:

== Основные определения ==
{{Определение
|definition= '''Рекурсивный язык (recursive language)''' <tex>L</tex> {{---}} язык, для которого существует программа <tex>p : \forall w \in L \Rightarrow p(w) = 1, \forall w \notin L \Rightarrow p(w) = 0</tex>.
}}

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

{{Определение
|definition= Класс всех разрешимых (рекурсивных) языков часто обозначается буквой <tex> \mathrm{R} </tex>.
}}

{{Определение
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''' ('''computable function'''), если существует программа <tex>p : \forall n \in D(f) \Rightarrow p(n) = f(n), \forall n \notin D(f) \Rightarrow p(n) = \bot </tex>.
}}

{{Определение
|id=uni
|definition='''Универсальный язык''' ('''universal language''') <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.
}}

== Некоторые разрешимые множества ==
{{Лемма
|id=st1
|statement=
Язык чётных чисел разрешим.
|proof=
Приведём программу, разрешающую язык чётных чисел:
<tex>p(i): </tex>
<tex>\mathrm{if} \ i \ mod \ 2 == 0 </tex>
<tex>\mathrm{return} \ 1 </tex>
<tex>\mathrm{else} </tex>
<tex>\mathrm{return} \ 0 </tex>

Заметим, что программа нигде не может зависнуть.
}}

== Некоторые неразрешимые множества ==

{{Лемма
|id=st1
|statement=
Универсальный язык неразрешим.
|proof=
Приведём доказательство от противного.

Пусть язык <tex>U</tex> разрешим, тогда существует программа <tex> u </tex> : <tex> \forall \langle p, x \rangle \in U \Rightarrow u(\langle p, x \rangle) = 1</tex>, <tex> \forall \langle p, x \rangle \notin U \Rightarrow u(\langle p, x \rangle) = 0</tex>.

Составим следующую программу:

<tex>r(x):</tex>
<tex> \mathrm{if} \ u(\langle x, x \rangle) == 1 </tex>
<tex>\mathrm{while} \ true </tex>
<tex> \mathrm{else} </tex>
<tex>\mathrm{return} \ 1 </tex>

Рассмотрим вызов <tex> r(r) </tex>:
* Eсли <tex> u(\langle r, r \rangle) = 1 </tex>, то условие <tex>\mathrm{if}</tex> выполнится и программа зависнет, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;
* Eсли <tex> u(\langle r, r \rangle) = 0 </tex>, то условие <tex>\mathrm{if}</tex> не выполнится и программа вернет <tex>1</tex>, но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

Из предположения о разрешимости универсального языка мы пришли к противоречию.
}}

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия — Рекурсивный язык]
* Методические указания к курсу ”Сложность вычислений” Гамова А.Н.

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

Викиконспекты - Вклад участника [ru]

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