Изменения

Перейти к: навигация, поиск

Разрешимые (рекурсивные) языки

13 байт убрано, 01:07, 12 апреля 2018
Нет описания правки
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
Допустим, что язык разрешим. Тогда напишем такую программу:
<code>
<tex>p(x){:}</tex>
'''if''' <tex>u(\mathrm{getSrc()}, x)</tex>
'''else'''
'''return''' 1
</code>
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> должна вернуть <tex> 1 </tex>, но по условию <tex>\mathrm{if} </tex> она зависает, а следовательно, не принадлежит универсальному языку.
Анонимный участник

Навигация