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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
}}
 
}}
  
=Примеры=
 
 
==Пример разрешимого множества==
 
==Пример разрешимого множества==
 
{{Утверждение
 
{{Утверждение
Строка 12: Строка 11:
 
Приведём программу, разрешающую язык чётных чисел:
 
Приведём программу, разрешающую язык чётных чисел:
 
  <tex>p(i)</tex>
 
  <tex>p(i)</tex>
  '''if''' остаток от деления i на 2 = 0
+
  '''if''' <tex> i \equiv 0 \  (mod \  2) </tex>
   '''return''' 1
+
   '''return''' <tex> 1 </tex>
 
  '''else'''
 
  '''else'''
   '''return''' 0
+
   '''return''' <tex> 0 </tex>
 
Заметим, что программа нигде не может зависнуть.
 
Заметим, что программа нигде не может зависнуть.
 
}}
 
}}
Строка 36: Строка 35:
  
 
  <tex>r(x)</tex>
 
  <tex>r(x)</tex>
  '''if''' u(<x, x>) = 1
+
  '''if''' <tex> u(\langle x, x \rangle) = 1 </tex>
   '''while''' true
+
   '''while''' <tex> true </tex>
 
  '''else'''
 
  '''else'''
   '''return''' 1
+
   '''return''' <tex> 1 </tex>
  
 
Теперь рассмотрим вызов <tex> r(r) </tex>.
 
Теперь рассмотрим вызов <tex> r(r) </tex>.
* Если <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''if''' выполнится и вызов зациклится. Но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>.
+
* Если <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''if''' выполнится и программа зависнет. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>.
* Если <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''if''' не выполнится и вызов вернёт <tex>1</tex>. Но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.
+
* Если <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''if''' не выполнится и программа вернет <tex>1</tex>. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.
  
 
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
 
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
 
}}
 
}}
 +
== Литература ==
 +
Н. К. Верещагин,  А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999

Версия 02:55, 16 декабря 2011

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


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

Утверждение:
Язык чётных чисел разрешим.
[math]\triangleright[/math]

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

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

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

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


Утверждение:
Универсальный язык неразрешим.
[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]

Литература

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999