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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
Строка 1: Строка 1:
 
== Основные определения ==  
 
== Основные определения ==  
 
{{Определение
 
{{Определение
|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>.
+
|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>.
 
}}
 
}}
  
Строка 11: Строка 11:
  
 
{{Определение
 
{{Определение
|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>.
+
|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''' (англ. ''computable''), если существует программа <tex>p : \forall n \in D(f) \Rightarrow p(n) = f(n), \forall n \notin D(f) \Rightarrow p(n) = \bot </tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition = Язык <tex>L</tex> называется ''разрешимым'', если существует такая функция <tex>f : \Sigma^* \to {0, 1} : x \in L \leftrightarrow f(x) = 1</tex> {{---}} вычислима.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|id=uni
 
|id=uni
|definition='''Универсальный язык''' ('''universal language''') <tex>\  U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.
+
|definition='''Универсальный язык''' (англ. ''universal language'') <tex>\  U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.
 
}}
 
}}
  

Версия 13:44, 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]

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

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