Изменения

1, \forall w \in L\\0, \forall w \notin L.

}}

Другими словами, ''универсальный язык'' {{---}} это язык всех таких пар "программа и её вход" таких, что программа на входе возвращает <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>\to</tex> "строка" == Примеры разрешимых множества множеств ==

<tex>p(i){: } </tex>

Для чисел <tex>e, \ \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье <ref>[http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]. Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon), которые создали свой алгоритм для нахождения цифр числа <tex>\pi</texref> в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, и предназначался тот алгоритм для нахождения цифр числа таким образом, возможно получить необходимый знак чисел <tex>e, \ \pi</tex>за конечное время.

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

<tex>p(r){: } </tex>

'''for'''(i = 0;; ++i1 .. <tex>\infty </tex>) '''if''' (getDigit(<tex>e</tex>, i) > getDigit(<tex>r</tex>, i)) <font color="green">// getDigit {{---}} функция, которая получает i-ую цифру вещественной части переданного числа</font>

Так как число <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''e' <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}}===Доказательство===

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

<tex>r(x){:} </tex> '''if''' <tex>u(\langle x, x \rangle) == 1 </tex> '''while''' (''true)'' '''else''' '''return''' 1

 ===Альтернативное доказательство с использованием теоремы о рекурсии===По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <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 />