3622
правки
Изменения
м
Напишем Допустим, что он разрешим. Тогда напишем такую программу:
Нет описания правки
|statement=[[Разрешимые (рекурсивные) языки#Пример неразрешимого множества | Универсальный язык]] неразрешим
|proof=
<code>
p(x):
<code>
p():
'''for''' i = 1..BB(<tex>|p|</tex>) + 1
do smth
</code>
Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(|p|) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.
}}
* [[wikipedia:Kolmogorov_complexity | Wikipedia {{---}} Kolmogorov_complexity]]
* [http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf Kolmogorov Complexity]
* [http://www.lektorium.tv/lecture/?id=13494 Дмитрий Ицыксон {{---}} Вычислимость и логика, Колмогоровская сложность]
[[Категория: Теория формальных языков]]
