Алгоритм аппроксимации сложности по Колмогорову - PullRequest
Новая
       15

Алгоритм аппроксимации сложности по Колмогорову

11 голосов
/ 19 августа 2010

Я ищу алгоритм, который может вычислить аппроксимацию колмогоровской сложности заданной входной строки. Таким образом, если K - это колмогоровская сложность строки S, а t представляет время, то функция будет вести себя примерно так: limit (t-> inf) [K_approx (t, S)] = K.

Ответы [ 5 ]

13 голосов
/ 19 августа 2010

Теоретически, программа может сходиться по колмогоровской сложности входной строки, когда время выполнения приближается к бесконечности.Это может работать, запуская каждую возможную программу параллельно, которая является длиной входной строки или короче.Когда программа заданной длины найдена, эта длина идентифицируется как минимальная длина, известная на данный момент, печатается, и больше программ> = эта длина не пробуется.Этот алгоритм (скорее всего) будет работать вечно, печатая все короче и короче, сходясь к точной колмогоровской сложности с учетом бесконечного времени.

Конечно, экспоненциальное количество программ очень интрацибельно.Более эффективный алгоритм - разместить гольф с кодом на StackOverflow .Несколько недостатков:

  • Для получения хороших результатов может потребоваться несколько дней.
  • Он использует огромное количество наших наиболее ценных вычислительных ресурсов, что приводит к потере производительности в тысячах долларов.
  • Результаты создаются с меньшей частотой с течением времени, поскольку ресурсы перенаправляются на другие вычисления .
  • Алгоритм завершается преждевременно для многих входов, что означает, что он не работает вообще.
1 голос
/ 20 августа 2010
1 голос
/ 19 августа 2010

Страница википедии для колмогоровской сложности содержит подраздел «Неисчислимость колмогоровской сложности» в разделе «Основные результаты».Это не является основной мерой, которую вы можете вычислить или даже приблизительно оценить.

Существуют лучшие способы достижения того, чего вы хотите, без сомнения.Если вам нужна мера случайности, вы можете попробовать двоичную энтропийную функцию.Сжимаемость с помощью одного из стандартных алгоритмов также может соответствовать требованиям.

1 голос
/ 19 августа 2010

Я думаю, это может сработать? Если кто-то видит ошибку, пожалуйста, укажите на нее. 

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;
0 голосов
/ 13 ноября 2010

Первая проблема, которую я замечаю, состоит в том, что «Колмогоровская сложность» не очень хорошо определена. Это зависит в некоторой степени от выбора того, как представлять программы. Итак, первое, что вам нужно сделать, это исправить некоторые кодировки программ (например, спецификация Джои Адамса, что программы должны быть написаны на J).

Когда у вас есть кодировка, алгоритм, который вы ищете, довольно прост. См. Ответ Джои для этого.

Но ситуация еще хуже, чем при экспоненциальном запуске многих программ. Каждая из этих программ может работать так долго, как вы можете себе представить (технически: время выполнения как размер входных данных функции может расти быстрее, чем любая рекурсивная функция). Более того, может случиться так, что некоторые из самых коротких программ - те, которые работают дольше всего. Таким образом, хотя параллельный подход будет приближаться к правильному значению с течением времени до бесконечности, он будет делать это невообразимо медленно.

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

Таким образом, короткий ответ «просто, просто используйте алгоритм Джоуи», но, если принять во внимание практичность, ответ «у вас нет шансов». В соответствии с рекомендациями rwong, вам лучше всего использовать алгоритм сжатия для больших нагрузок.

...