3622
правки
Изменения
гёдель
|statement = В любой "достаточно богатой системе" существует истинное недоказуемое утверждение.
|proof =
Поясним, что это значит. Так как любой язык программирования эквивалентен [[Машина Тьюринга | машине Тьюринга]], то всё связанное с ним кодируется в [[Теории первого порядка | логике первого порядка]] с [[Классы_чисел#Аксиомы_Пеано | аксиомами Пеано]] (для этого достаточно, чтобы программа умела прибавлять к числу единицу и вызывать подпрограммы), поэтому можно в терминах программ получать утверждения, эквивалентные тем, что строил Гёдель.
Можно переформулировать теорему следующим образом: невозможно доказать, что <tex> p(x) = \perp </tex>.
</code>
}}
== Теорема о неподвижной точке ==
Зафиксируем главную нумерацию <tex> W </tex>. Обозначим за <tex> W_n </tex> множество слов, допускаемых программой с номером <tex> n </tex>.
== Ссылки ==
* [[wikipedia:Kolmogorov_complexity | Wikipedia {{---}} Kolmogorov_complexity]]
* [http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf | Kolmogorov Complexity]
[[Категория: Теория формальных языков]]
