Изменения
Нет описания правки
Существует [[Отображения#Свойства отображений | биекция]] между строками и натуральными числами.
|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
}}
== Примеры неразрешимых множества множеств ==
{{Утверждение
|statement=
Универсальный язык неразрешим.
Приведём доказательство от противного.
Из предположения о разрешимости универсального языка мы пришли к противоречию.
===Альтернативное доказательство с использованием теоремы о рекурсии===По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <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>, значит, пара не принадлежит. Опять получили противоречие.
== Примечания ==
