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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Некоторые разрешимые множества)
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 10 участников)
Строка 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>L</tex>  как  проблему,  то  проблема  называется  ''разрешимой'',  если  язык  <tex>L</tex>  ''рекурсивный''.  В  противном  случае  проблема  называется  ''неразрешимой''. Но часто данные понятия просто отождествляются.
 
  
{{Определение
+
<tex>p(w) = \begin{cases}
|definition= Класс всех разрешимых (рекурсивных) языков часто обозначается буквой <tex> \mathrm{R} </tex>.
+
1, \ w \in L \\
 +
0, \ w \notin L
 +
\end{cases}
 +
</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>.
 
}}
 
}}
 +
Если  мы  рассматриваем  язык  <tex>L</tex>  как  проблему,  то  проблема  называется  ''разрешимой'',  если  язык  <tex>L</tex>  ''рекурсивный''.  В  противном  случае  проблема  называется  ''неразрешимой''. Но часто данные понятия просто отождествляются.
  
 
{{Определение
 
{{Определение
|definition = Язык <tex>L</tex> называется ''разрешимым'', если существует такая функция <tex>f : \Sigma^* \to {0, 1} : x \in L \leftrightarrow f(x) = 1</tex> {{---}} вычислима.
+
|definition= '''Класс всех разрешимых (рекурсивных) языков''' (англ. ''Class of decidable (recursive) languages'') часто обозначается буквой <tex> \mathrm{R} </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>.
 
}}
 
}}
  
== Примеры разрешимых множества ==
+
Другими словами, ''универсальный язык'' {{---}} это язык всех таких пар "программа и её вход", что программа на входе возвращает <tex>1</tex>.
 +
 
 +
Рассмотрим данное определение более детально, для чего докажем вспомогательную лемму:
 +
 
 
{{Лемма
 
{{Лемма
 +
|statement=
 +
Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.
 +
|proof=
 +
Приведем пример такой биекции: занумеруем подряд все строки длины <tex>1</tex>, затем все строки длины <tex>2</tex> и так далее {{---}} нумерация названий столбцов в <tex>Excel</tex>, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.
 +
}}
 +
 +
Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:
 +
 +
<tex>2^{\mathtt{code}} \cdot 3^{\mathtt{input}}</tex>, где <tex>\mathtt{code}, \ \mathtt{input}</tex> {{---}} есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.
 +
 +
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
 +
 +
== Примеры разрешимых множеств ==
 +
{{Утверждение
 
|id=st1
 
|id=st1
 
|statement=
 
|statement=
Строка 30: Строка 48:
 
|proof=
 
|proof=
 
Приведём программу, разрешающую язык чётных чисел:
 
Приведём программу, разрешающую язык чётных чисел:
  <tex>p(i): </tex>
+
  <tex>p(i) {:} </tex>
<tex>\mathrm{if} \ i \ mod \ 2 == 0 </tex>
+
  '''if''' <tex>i \ \bmod \ 2 == 0 </tex>
  <tex>\mathrm{return} \ 1 </tex>
+
    '''return''' 1
<tex>\mathrm{else} </tex>
+
  '''else'''
  <tex>\mathrm{return} \ 0 </tex>
+
    '''return''' 0
  
 
Заметим, что программа нигде не может зависнуть.
 
Заметим, что программа нигде не может зависнуть.
 
}}
 
}}
  
== Некоторые неразрешимые множества ==
 
  
{{Лемма
+
{{Утверждение
 +
|statement=
 +
Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\pi</tex>, разрешимо.
 +
|proof=
 +
Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье<ref>[http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]</ref>, таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex> за конечное время.
 +
 
 +
Десятичное представление рационального числа <tex>r</tex> может быть получено с любой точностью.
 +
 
 +
Приведем программу, разрешающую данную проблему для числа <tex>e</tex>:
 +
 +
<tex>p(r) {:} </tex>
 +
  '''if''' (<tex>r</tex> < 2)
 +
    '''return''' 1
 +
  '''if''' (<tex>r</tex> > 3)
 +
    '''return''' 0
 +
  '''for''' (i = 1 .. <tex>\infty </tex>) 
 +
    '''if''' (getDigit(<tex>e</tex>, i) > getDigit(<tex>r</tex>, i))  <font color="green">// getDigit {{---}} функция, которая получает i-ую цифру вещественной части переданного числа</font>
 +
      '''return''' 1
 +
    '''if''' (getDigit(<tex>e</tex>, i) < getDigit(<tex>r</tex>, i))
 +
      '''return''' 0
 +
Так как число <tex>e</tex> иррационально, то ответ будет найден за конечное время.
 +
}}
 +
 
 +
{{Утверждение
 +
|statement=
 +
Множество тех <tex>n</tex>, для которых в числе <tex>\pi</tex> есть не менее <tex>n</tex> девяток подряд, разрешимо.
 +
|proof=
 +
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
 +
Рассмотрим все программы семейства:
 +
<tex>p_0(i) {:} </tex>
 +
  '''return''' 1
 +
 
 +
<tex>p_1(i) {:} </tex>
 +
  '''if''' <tex>i < 1 </tex>
 +
    '''return''' 1
 +
  '''else'''
 +
    '''return''' 0
 +
 
 +
<tex>p_2(i) {:} </tex> 
 +
  '''if''' <tex>i < 2 </tex>
 +
    '''return''' 1
 +
  '''else'''
 +
    '''return''' 0
 +
 
 +
<tex>\dots</tex>   
 +
 
 +
<tex>p_k(i) {:} </tex> 
 +
  '''if''' <tex>i < k </tex>
 +
    '''return''' 1
 +
  '''else'''
 +
    '''return''' 0
 +
 
 +
<tex>\dots</tex>
 +
 +
По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
 +
}}
 +
 
 +
== Примеры неразрешимых множеств ==
 +
 
 +
{{Утверждение
 
|id=st1
 
|id=st1
 
|statement=
 
|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>U</tex> разрешим, тогда существует программа
 +
 
 +
<tex>u(\langle p, x \rangle) = \begin{cases}
 +
1, \ \langle p, x \rangle \in U \\
 +
0, \ \langle p, x \rangle \notin U
 +
\end{cases}
 +
</tex>
 +
 
  
 
Составим следующую программу:
 
Составим следующую программу:
  
  <tex>r(x):</tex>
+
  <tex>r(x) {:} </tex>
<tex> \mathrm{if} \ u(\langle x, x \rangle) == 1 </tex>
+
  '''if''' <tex>u(\langle x, x \rangle) == 1 </tex>
  <tex>\mathrm{while} \ true </tex>
+
    '''while''' ''true''
<tex> \mathrm{else} </tex>
+
  '''else'''
  <tex>\mathrm{return} \ 1 </tex>
+
    '''return''' 1
  
 
Рассмотрим вызов <tex> r(r) </tex>:
 
Рассмотрим вызов <tex> r(r) </tex>:
Строка 63: Строка 147:
  
 
Из предположения о разрешимости универсального языка мы пришли к противоречию.
 
Из предположения о разрешимости универсального языка мы пришли к противоречию.
}}
+
 
 +
===Альтернативное доказательство с использованием теоремы о рекурсии===
 +
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
 +
Допустим, что язык разрешим. Тогда напишем такую программу:
 +
 
 +
  <tex>p(x){:}</tex>
 +
    '''if''' <tex>u(\mathrm{getSrc()}, x)</tex>
 +
      '''while''' ''true''
 +
    '''else'''
 +
      '''return''' 1
 +
 
 +
 
 +
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> должна вернуть <tex> 1 </tex>, но по условию <tex>\mathrm{if} </tex> она зависает, а следовательно, не принадлежит универсальному языку.
 +
 
 +
Если же <tex> u(p, x) \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex>
 +
\langle p, x \rangle </tex> принадлежит универсальному языку, но <tex> u(p, x) \neq 1 </tex>, значит, пара не принадлежит. Опять получили противоречие.
 +
 
 +
== Примечания ==
 +
 
 +
<references />
  
 
== Источники информации ==
 
== Источники информации ==
Строка 69: Строка 172:
 
* [http://en.wikipedia.org/wiki/Recursive_language Wikipedia — Recursive language]
 
* [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 Википедия — Рекурсивный язык]
 
* [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 Википедия — Рекурсивный язык]
* Методические указания к курсу  ”Сложность вычислений” Гамова  А.Н.
+
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]

Текущая версия на 19:23, 4 сентября 2022

Основные определения

Определение:
Рекурсивный язык (англ. recursive language) [math]L[/math] — язык, для которого существует программа [math]p(w) = \begin{cases} 1, \ w \in L \\ 0, \ w \notin L \end{cases} [/math]


Определение:
Язык [math]L[/math] называется разрешимым, если существует такая вычислимая функция [math]f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1[/math].

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


Определение:
Класс всех разрешимых (рекурсивных) языков (англ. Class of decidable (recursive) languages) часто обозначается буквой [math] \mathrm{R} [/math].


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


Другими словами, универсальный язык — это язык всех таких пар "программа и её вход", что программа на входе возвращает [math]1[/math].

Рассмотрим данное определение более детально, для чего докажем вспомогательную лемму:

Лемма:
Существует биекция между строками и натуральными числами.
Доказательство:
[math]\triangleright[/math]
Приведем пример такой биекции: занумеруем подряд все строки длины [math]1[/math], затем все строки длины [math]2[/math] и так далее — нумерация названий столбцов в [math]Excel[/math], таким образом, каждому натуральному числу соответствует некоторая строка и наоборот.
[math]\triangleleft[/math]

Биекция между строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текст входных данных" в качестве аргументов функций. Передавать можно в следующем виде:

[math]2^{\mathtt{code}} \cdot 3^{\mathtt{input}}[/math], где [math]\mathtt{code}, \ \mathtt{input}[/math] — есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.

Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом [math]\Sigma[/math].

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

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

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

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


Утверждение:
Множество всех рациональных чисел, меньших числа [math]e[/math] (основания натуральных логарифмов) или [math]\pi[/math], разрешимо.
[math]\triangleright[/math]

Для чисел [math]e, \ \pi[/math] существуют различные техники нахождения их точного представления, одна их которых описана в статье[1], таким образом, возможно получить необходимый знак чисел [math]e, \ \pi[/math] за конечное время.

Десятичное представление рационального числа [math]r[/math] может быть получено с любой точностью.

Приведем программу, разрешающую данную проблему для числа [math]e[/math]:

[math]p(r) {:} [/math]
  if ([math]r[/math] < 2)
    return 1
  if ([math]r[/math] > 3)
    return 0
  for (i = 1 .. [math]\infty [/math])  
    if (getDigit([math]e[/math], i) > getDigit([math]r[/math], i))  // getDigit — функция, которая получает i-ую цифру вещественной части переданного числа
      return 1
    if (getDigit([math]e[/math], i) < getDigit([math]r[/math], i))
      return 0
Так как число [math]e[/math] иррационально, то ответ будет найден за конечное время.
[math]\triangleleft[/math]
Утверждение:
Множество тех [math]n[/math], для которых в числе [math]\pi[/math] есть не менее [math]n[/math] девяток подряд, разрешимо.
[math]\triangleright[/math]

Предположим, что в числе [math]\pi[/math] встречается [math]k[/math] девяток подряд, тогда, логично, что встречается и любое число девяток меньших [math]k[/math]. Рассмотрим все программы семейства:

[math]p_0(i) {:} [/math]
  return 1
[math]p_1(i) {:} [/math]
  if [math]i \lt  1 [/math]
    return 1
  else
    return 0
[math]p_2(i) {:} [/math]  
  if [math]i \lt  2 [/math]
    return 1
  else
    return 0

[math]\dots[/math]

[math]p_k(i) {:} [/math]  
  if [math]i \lt  k [/math]
    return 1
  else
    return 0

[math]\dots[/math]

По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
[math]\triangleleft[/math]

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

Утверждение:
Универсальный язык неразрешим.

Доказательство

Приведём доказательство от противного.

Пусть язык [math]U[/math] разрешим, тогда существует программа

[math]u(\langle p, x \rangle) = \begin{cases} 1, \ \langle p, x \rangle \in U \\ 0, \ \langle p, x \rangle \notin U \end{cases} [/math]


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

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

Рассмотрим вызов [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] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Допустим, что язык разрешим. Тогда напишем такую программу:

 [math]p(x){:}[/math]
   if [math]u(\mathrm{getSrc()}, x)[/math]
     while true
   else
     return 1


Если [math] u(p, x) = 1 [/math], тогда программа [math] p [/math] на входе [math] x [/math] должна вернуть [math] 1 [/math], но по условию [math]\mathrm{if} [/math] она зависает, а следовательно, не принадлежит универсальному языку.

Если же [math] u(p, x) \neq 1 [/math], то мы пойдём во вторую ветку условного оператора и вернём [math] 1 [/math], значит, пара [math] \langle p, x \rangle [/math] принадлежит универсальному языку, но [math] u(p, x) \neq 1 [/math], значит, пара не принадлежит. Опять получили противоречие.

Примечания

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