3622
правки
Изменения
гёдель
== Busy beaver ==
== Аналог I теоремы Гёделя о неполноте ==
{{Теорема
|id = thGI.
|statement = В любой "достаточно богатой системе" существует истинное недоказуемое утверждение.
|proof =
Можно переформулировать теорему следующим образом: невозможно доказать, что <tex> p(x) = \pepr </tex>.
Тогда напишем такую программу:
<code>
p(x):
'''foreach''' q <tex> \in ~ \Sigma^* </tex>
'''if''' q proves "p(x) зависает"
exit
</code>
}}
== Аналог II теоремы Гёделя о неполноте ==
== Теорема о неподвижной точке ==
Зафиксируем
