Изменения

Другими словами, ''универсальный язык'' {{---}} это язык всех таких пар "программа и её вход" таких, что программа на входе возвращает <tex>1</tex>.

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

{{Лемма|statement=Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.|proof=Приведем пример такой биекции: занумеруем подряд все строки длины <tex>2^{\text{code}} * 3^{\text{input}}1</tex>, где затем все строки длины <tex>code, \ input2</tex> и так далее {{---}} есть биекция нумерация названий столбцов в <tex>Excel</tex>, таким образом, каждому натуральному числу соответствует некоторая строка и наоборот. }} Биекция между текстом строками и натуральными числами нам нужна, чтобы передавать пары "текст программы, текстом текст входных данных и натуральным числом (например, " в качестве аргументов функций. Передавать можно занумеровать подряд все строки длинны в следующем виде:  <tex>12^{\mathtt{code}} \cdot 3^{\mathtt{input}}</tex>, затем все строки длинны где <tex>2\mathtt{code}, \ \mathtt{input}</tex> и так далее {{---}} нумерация названий столбцов в <tex>Excel</tex>)есть натуральные числа, соответствующие тексту программы и тексту входных данных соответственно.

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

Для чисел <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> за конечное время.

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

'''if''' <tex>i \leqslant < 1 </tex>

'''if''' <tex>i \leqslant k < 2 </tex>

'''if''' <tex>i \leqslant < k </tex>

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

|proof}}===Доказательство===

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