313
правок
Изменения
→Альтернативное доказательство с использованием теоремы о рекурсии
===Альтернативное доказательство с использованием теоремы о рекурсии===
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
<tex> A </tex> {{---}} разрешимое семейство языков.
<code>
<tex>propA(code){:}</tex>
// программа, разрешающее свойство языка <tex> A </tex>
<tex>f(x){:}</tex>
// такая программа <tex> f </tex>, что <tex>f \in A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
<tex>g(x){:}</tex>
// такая программа <tex> g </tex>, что <tex>g \notin A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
<tex>p(x){:}</tex> '''if''' <tex>propA(\mathrm{getSrc()})</tex> '''return''' <tex>g(x)</tex>
'''else'''
'''return''' <tex>f(x)</tex>
</code>
