Алгоритм аппроксимации сложности Колмогорова
Я ищу алгоритм, который может вычислить приближение колмогоровской сложности данной входной строки. Итак, если K - колмогоровская сложность строки S, а t представляет время, тогда функция будет вести себя примерно так ... limit (t-> inf) [K_approx (t, S)] = K.
4 ответа
Я думаю, это может сработать? Если кто-то увидит ошибку, пожалуйста, укажите на нее.
function KApprox(S:string,t:integer,TapeSizeMax:integer) : Turing Machine of size k
begin
// An abstract data type that represents a turing machine of size k
var TM(k:integer) : Turing Machine of size k;
var TMSmallest(k:integer) : Turing Machine of size k;
var j : integer;
var i : integer;
for (j = t to 0 step -1) // reduce the time counter by 1
begin
for (i = TMax to 1 step -1) // go to the next smaller size of TM
begin
foreach (TM(i)) // enumerate each TM of size i
begin
if (TM(i).halt(TapeSizeMax) == true) and (TM(i).output() == S) then
begin
if (sizeof(TM(i)) < sizeof(TMSmallest(i))) then
TMSmallest(i): = TM(i);
end;
end;
end;
end;
return TMSmallest;
end;
На странице википедии, посвященной сложности Колмогорова, есть подраздел "Невычислимость сложности Колмогорова" в разделе "Основные результаты". Она не предназначена для того, чтобы быть базовой мерой, которую можно вычислить или даже продуктивно приблизить.
Несомненно, есть лучшие способы достижения желаемого. Если вам нужна мера случайности, вы можете попробовать двоичную функцию энтропии. Сжимаемость по одному из стандартных алгоритмов также может подойти.
Теоретически программа может сходиться на колмогоровской сложности входной строки, когда время выполнения приближается к бесконечности. Он может работать, если параллельно запускать все возможные программы, длина которых равна длине входной строки или короче. Когда программа заданной длины найдена, эта длина определяется как минимальная длина, известная на данный момент, печатается, и больше не пробуются программы> = этой длины. Этот алгоритм (скорее всего) будет работать вечно, печатая все более и более короткие длины, сходясь на точной сложности Колмогорова за бесконечное время.
Конечно, выполнение экспоненциального числа программ очень легко адаптируется. Более эффективный алгоритм - разместить код гольфа на StackOverflow . Несколько недостатков:
- Для получения хороших результатов может пройти несколько дней.
- Он использует огромное количество наших самых ценных вычислительных ресурсов, что приводит к потере производительности в тысячи долларов.
- Результаты выдаются с меньшей частотой с течением времени, поскольку ресурсы перенаправляются на другие вычисления .
- Алгоритм преждевременно завершается для многих входов, что означает, что он не работает в целом.
Похоже, Рэй Соломонов проделал большую работу в этой области.