Изменения
Нет описания правки
}}
Другими словами, ''универсальный язык'' {{---}} это язык всех программ таких пар "программа и их входных данныхеё вход", что программа на которых программа входе возвращает <tex>1</tex>.
Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.
== Примеры разрешимых множества множеств ==
{{Утверждение
|id=st1
Множество всех рациональных чисел, меньших числа <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> может быть получено с любой точностью.
'''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))
{{Утверждение
|statement=
|proof=
Предположим, что в числе <tex>\pi</tex> встречается <tex>k</tex> девяток подряд, тогда, логично, что встречается и любое число девяток меньших <tex>k</tex>.
Рассмотрим все программы семейства:
<tex>p_0(i) {:} </tex>
<tex>p_1(i) {:} </tex>
'''if''' <tex>i \leq < 1 </tex>
'''return''' 1
'''else'''
<tex>p_2(i) {:} </tex>
'''if''' <tex>i \leq k < 2 </tex>
'''return''' 1
'''else'''
<tex>\dots</tex>
<tex>p_np_k(i) {:} </tex> '''if''' <tex>i \leq n < k </tex>
'''return''' 1
'''else'''
'''return''' 0
<tex>\dots</tex>
По доказанному выше, какая-то программа из этого семейства будет разрешителем для искомого множества. Значит, искомое множество разрешимо.
}}
== Примеры неразрешимых множества множеств ==
{{Утверждение
|statement=
Универсальный язык неразрешим.
Приведём доказательство от противного.
<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 />
* [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 Википедия — Рекурсивный язык]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
