313
правок
Изменения
→Теорема о неподвижной точке
Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция <tex>g(x)</tex>, являющаяся <tex>\equiv</tex> {{---}} продолжением функции <tex>f(x)</tex>. Давайте зададим функцию <tex>t(x)</tex> следующим образом: <tex>t(x) = h(g(x))</tex>, где <tex>h(x)</tex> - искомая всюду определенная, вычислимая функция, не имеющая <tex>\equiv</tex> {{---}} неподвижных точек. Тогда <tex>t(x)</tex> всюду отличается от <tex>f(x)</tex> (в силу того, что <tex>h(x)</tex> не имеет неподвижных точек.) Получили противоречие, из чего следует, что такой функции <tex>h</tex> не существует.
}}
{{Утверждение
|id=идентификатор (необязательно), пример: proposalF.
|statement = <tex> \exists n : W_n = \{n\} </tex>, где <tex> W_n </tex> {{---}} множество слов, допускаемых программой с номером <tex> n </tex>.
|proof=
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
Напишем такую программу:
<code>
p(q):
'''if''' p.getSrc() == q.getSrc()
'''return''' 1
'''else'''
'''while''' ''true''
</code>
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
}}
