Колмогоровская сложность

Материал из Википедии — свободной энциклопедии

Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите её в соответствии с правилами написания статей.

Неформально, колмогоровская сложность последовательности из нулей и единиц — это длина самой короткой программы, которая может породить эту последовательность.

В дальнейшем, мы будем измерять длины всех объектов в битах. Для определения сложности мы начнём с элементарных замечаний. Начнём с описания бинарной последовательности (строки). Описание бинарной последовательности s — это просто программа, написанная как строка бит, которая производит последовательность s как результат. Принимая во внимание все возможные программы, которые генерируют последовательность s и выбирая кратчайшую, мы получим минимальное описание последовательности s, обозначаемое как d(s). (Если существует более одной программы одинаковой длины, выберем в качестве d(s) первую из них в лексикографическом порядке.) Колмогоровская сложность s, записывается K(s), и

K(s) = | d(s) | .

Другими словами, K(s) — это длина минимального описания s.

[править] Ссылки

• Курс по колмогоровской сложности (пособие на английском языке)(англ.)
• Доклад по колмогоровской сложности (определения, свойства, понятие условной колмогоровской сложности)
• Ученые, объединенные научным интересом «колмогоровская сложность»

Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её.