Изменения

|definition=Язык <tex>L</tex> называется '''разрешимымРекурсивный язык''' (англ. '''рекурсивным'recursive language'')<tex>L</tex> {{---}} язык, если для которого существует такая программа  <tex> p (w) = \begin{cases}1, \ w \in L \\0, \ w \notin L\end{cases}</tex>}} {{Определение|definition = Язык <tex>L</tex> называется '''разрешимым''', что если существует такая [[Вычислимые функции | вычислимая]] функция <tex> f : \Sigma^* \to \{0, 1\forall w } : x \in L: p\Leftrightarrow f(wx) = 1</tex>.}}Если мы рассматриваем язык <tex>L</tex> как проблему, а то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются. {{Определение|definition= '''Класс всех разрешимых (рекурсивных) языков''' (англ. ''Class of decidable (recursive) languages'') часто обозначается буквой <tex> \forall w mathrm{R} </tex>.}} {{Определение|id=uni|definition='''Универсальный язык''' (англ. ''universal language'') <tex> \ U = \{\langle p, x \rangle \ |\notin L: p(wx) = 01\} </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>. == Примеры разрешимых множеств ==

<tex>p(i){:} </tex> '''if''' <tex> (i \ mod \ bmod \ 2 == 0) </tex> '''return''' <tex> 1 </tex> '''else''' '''return''' <tex> 0 </tex> 

{{ОпределениеУтверждение|definitionstatement=Язык Множество всех рациональных чисел, меньших числа <tex>e</tex> (основания натуральных логарифмов) или <tex>\ pi</tex>, разрешимо.|proof= U Для чисел <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>\langle ppi</tex> есть не менее <tex>n</tex> девяток подряд, x \rangle \ разрешимо.|proof=Предположим, что в числе <tex>\ ppi</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(xi) = {:} </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> По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.

|proof}}===Доказательство===Доказательство Приведём доказательство от противного. <br/> Пусть язык <tex> U </tex> разрешим. <br/>Тогда , тогда существует такая программа  <tex> u </tex>, что <tex> \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = \begin{cases}1</tex>, а <tex> \forall \langle p, x \rangle \notin in U: u(\\0, \ \langle p, x \rangle) = 0\notin U\end{cases}</tex>. <br/>  

<tex>r(x){:} </tex> '''if''' <tex> u(\langle x, x \rangle) == 1 </tex> '''while''' <tex> ''true </tex>'' '''else''' '''return''' 1 Рассмотрим вызов <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>.

Теперь рассмотрим вызов <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) = 0 </tex>, то условие '''if''' не выполнится и программа вернет <tex>1</tex>. Но так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>Из предположения о разрешимости универсального языка мы пришли к противоречию.

Таким образом===Альтернативное доказательство с использованием теоремы о рекурсии===По [[Теорема о рекурсии | теореме о рекурсии]], из предположения о разрешимости универсального языка мы пришли к противоречиюпрограмма может знать свой исходный код. Значит, в неё можно написать функцию <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 /> == Источники информации ==* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 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 Википедия — Рекурсивный язык]  [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]]