3622
правки
Изменения
→Колмогоровская сложность
|definition='''Колмогоровской сложностью''' строки <tex> x </tex> называется функция <tex> K(x) </tex>, которая равна минимальной длине программы <tex> p : p(\varepsilon) = x </tex>.
}}
Сложность считается в каком-то фиксированном языке программирования. Так, например, у языков C++ и Python будет разная колмогоровская сложность одной программы.
=== Пример ===
Колмогоровская сложность программы, выводящей <tex> n </tex> нулей <tex> K(0^n) \leqslant n + c </tex>. Просто программа, в которой записано <tex> n </tex> нулей. Но можно записать и более короткую программу для больших <tex> n </tex> со сложностью <tex> K(0^n) \leqslant \log{n} + c </tex>, например вот такую:
