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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавил id к определению универсального языка, чтобы ссылаться на него из других конспектов)
(Источники)
Строка 47: Строка 47:
 
}}
 
}}
  
== Источники ==
+
== Источники информации ==
 
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
 
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]

Версия 11:14, 7 января 2015

Определение:
Язык [math]L[/math] называется разрешимым (рекурсивным, recursive language), если существует такая программа [math] p [/math], что [math] \forall w \in L: p(w) = 1[/math], а [math] \forall w \notin L: p(w) = 0[/math]. Класс всех разрешимых языков часто обозначается через [math] \mathrm{R} [/math].


Пример разрешимого множества

Лемма:
Язык чётных чисел разрешим.
Доказательство:
[math]\triangleright[/math]

Приведём программу, разрешающую язык чётных чисел:

[math]p(i):[/math]
if [math] i \  mod \  2 == 0 [/math]
  return [math] 1 [/math]
else
  return [math] 0 [/math]
Заметим, что программа нигде не может зависнуть.
[math]\triangleleft[/math]

Пример неразрешимого множества

Определение:
Язык [math]\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} [/math] называется универсальным (universal language).


Лемма:
Универсальный язык неразрешим.
Доказательство:
[math]\triangleright[/math]

Приведём доказательство от противного.
Пусть язык [math] U [/math] разрешим. Тогда существует такая программа [math] u [/math], что [math] \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = 1[/math], а [math] \forall \langle p, x \rangle \notin U: u(\langle p, x \rangle) = 0[/math].
Составим следующую программу:

[math]r(x):[/math]
if [math] u(\langle x, x \rangle) == 1 [/math]
  while [math] true [/math]
else
  return [math] 1 [/math]

Теперь рассмотрим вызов [math] r(r) [/math]:

  • если [math] u(\langle r, r \rangle) = 1 [/math], то условие if выполнится и программа зависнет. Но так как программа [math] u [/math] разрешает универсальный язык, [math] u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1[/math];
  • если [math] u(\langle r, r \rangle) = 0 [/math], то условие if не выполнится и программа вернет [math]1[/math]. Но так как программа [math] u [/math] разрешает универсальный язык, [math] u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1[/math].
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
[math]\triangleleft[/math]

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