колмогоровская сложность для сжатия с потерями

[ded_maxim]

А вот, оказывается, японцы Мурамацу и Каная придумали обобщение сложности по Колмогорову для lossy compression! Определяется для данной последовательности X^n = (X_1,...,X_n) и для заданного уровня потерь D как минимальная длина программы для универсальной машины Тьюринга, с помощью которой можно получить аппроксимацию X^n с точностью D. Если X^n это кусок стационарного эргодического процесса, то эта сложность равна примерно nR(D), где R(D) -- функция зависимости скорости передачи от искажения по Шеннону. (Связь с эпсилон-энтропией etc.) Круто (хотя и совершенно бесполезно с практической точки зрения)!

Comments

[ded-maxim.livejournal.com]

Ага, ага, скажи это П. Витаньи (http://homepages.cwi.nl/~paulv/). И потом, если универсальная машина Тьюринга не имеет отношения ни к чему практическому, то, выходит, Минский зря столько времени потратил, чтоб придумать наиболее компактную ее форму? И язык программирования Brainfuck (http://www.muppetlabs.com/~breadbox/bf/) существует исключительно для мозгоебства?