February 17th, 2021

  • mns2012

Сложность

Предположим, существует некоторый объект Х, сложность которого нужно оценить. По теории Колмогорова, вводится язык λ описания объектов. На этом языке могут быть созданы различные программы для описания Х. Сложность C(Х) есть длина самой короткой программы описания Х. В теории показывается, что C(X) не сильно зависит от λ. Сложность по Колмогорову не является вычислимой, её можно лишь оценивать или ... угадывать.

В рассуждениях о сложности удобно оперировать строками, предполагая, что каждому объекту реального мира можно поставить в соответствие строку описания. Например, описать объект можно, указав координаты и импульсы в данный момент времени всех составляющих его атомов. Таким образом, сложность объекта можно оценить по сложности строки описания. Строками же представляются и программы, ведь программа — не что иное, как запись инструкций обработчику или исполнителю.

Collapse )