3622
правки
Изменения
busy beaver
== Busy beaver ==
{{Утверждение
|id=proposalU.
|statement=Функция [[Busy beaver]] невычислима.
|proof= Предположим, что это так. Тогда напишем такую программу
<code>
p():
'''for''' i = 1..BB(p) + 1
do smth
</code>
Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(p) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.
}}
== Аналог I теоремы Гёделя о неполноте ==
{{Теорема
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
}}
== Ссылки ==
* [[wikipedia:Kolmogorov_complexity | Wikipedia {{---}} Kolmogorov_complexity]]
* [http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf | Kolmogorov Complexity]
[[Категория: Теория формальных языков]]
