Thuật toán xấp xỉ phức tạp Kolmogorov Thuật toán

Question

Tôi đang tìm một thuật toán có thể tính toán độ phức tạp Kolmogorov gần đúng của chuỗi đầu vào đã cho. Vì vậy, nếu K là độ phức tạp Kolmogorov của một chuỗi S, và t đại diện cho thời gian, thì hàm sẽ hành xử như thế này .. giới hạn (t-> inf) [K_approx (t, S)] = K.

Answer 1

In lý thuyết, một chương trình có thể hội tụ vào độ phức tạp Kolmogorov của chuỗi đầu vào của nó khi thời gian chạy tiến tới vô cùng. Nó có thể hoạt động bằng cách chạy mọi chương trình có thể song song đó là độ dài của chuỗi đầu vào hoặc ngắn hơn. Khi tìm thấy một chương trình có độ dài đã cho, độ dài đó được xác định là độ dài tối thiểu được biết đến hiện tại, được in và không còn chương trình nào khác> = độ dài đó được thử. Thuật toán này sẽ (rất có thể) chạy mãi mãi, in độ dài ngắn hơn và ngắn hơn, hội tụ vào độ phức tạp Kolmogorov chính xác cho thời gian vô hạn.

Tất nhiên, việc chạy số lượng chương trình theo cấp số nhân rất khó hiểu. Một thuật toán hiệu quả hơn là đăng một code golf on StackOverflow. Một vài nhược điểm:

• Có thể mất vài ngày trước khi có kết quả tốt.
• Nó sử dụng một lượng lớn tài nguyên máy tính có giá trị nhất của chúng tôi, tốn hàng ngàn đô la trong việc mất năng suất.
• Kết quả được tạo ra với tần suất ít hơn theo thời gian khi tài nguyên được chuyển hướng đến othercomputations.
• Thuật toán terminatesprematurely cho nhiều đầu vào, có nghĩa là nó không hoạt động nói chung.

Answer 2

Tôi nghĩ điều này có thể hiệu quả? Nếu ai đó thấy lỗi, vui lòng chỉ ra lỗi.

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; 

Answer 3

Các wikipedia page cho Kolmogorov phức tạp có một tiểu mục mang tên "Incomputability của Kolmogorov phức tạp", dưới sự "kết quả cơ bản". Đây không phải là một biện pháp cơ bản mà bạn có thể tính toán, hoặc thậm chí gần đúng một cách hiệu quả.

Có những cách tốt hơn để đạt được những gì bạn muốn, không nghi ngờ gì. Nếu một phép đo ngẫu nhiên là những gì bạn muốn, bạn có thể thử hàm entropy nhị phân. Độ nén của một trong các thuật toán chuẩn cũng có thể phù hợp với hóa đơn.

Answer 4

Dường như Ray Solomonoff đã làm rất nhiều công việc trong lĩnh vực này.

Publications of Ray Solomonoff

Inductive Inference Theory - A Unified Approach to Problems in Pattern Recognition and Artificial Intelligence.

Does Algorithmic Probability Solve the Problem of Induction?

Answer 5

Vấn đề đầu tiên mà tôi nhận thấy là "các Kolmogorov phức tạp" không được xác định rõ. Nó phụ thuộc vào mức độ nào đó về việc lựa chọn cách biểu diễn các chương trình. Vì vậy, điều đầu tiên bạn cần làm là sửa một số mã hóa các chương trình (ví dụ, đặc tả của Joey Adams là các chương trình được viết bằng J).

Khi bạn đã mã hóa, thuật toán bạn đang tìm kiếm khá đơn giản. Xem câu trả lời của Joey cho điều đó.

Nhưng tình hình còn tồi tệ hơn việc phải chạy nhiều chương trình theo cấp số nhân. Mỗi chương trình có thể chạy miễn là bạn có thể tưởng tượng (về mặt kỹ thuật: thời gian chạy khi kích thước đầu vào chức năng có thể tăng nhanh hơn bất kỳ hàm đệ quy nào).Hơn nữa, nó có thể là trường hợp một số chương trình ngắn nhất là những chương trình chạy dài nhất. Vì vậy, trong khi cách tiếp cận song song sẽ tiếp cận giá trị đúng như thời gian đi đến vô cùng, nó sẽ làm như vậy một cách không tưởng tượng được từ từ.

Bạn có thể dừng chương trình sớm, cho rằng xấp xỉ tại thời điểm đó là đủ tốt. Tuy nhiên, bạn không có ý tưởng nói chung là tốt như thế nào xấp xỉ. Trong thực tế, có những định lý cho thấy bạn không bao giờ có thể biết.

Vì vậy, câu trả lời ngắn gọn là "dễ dàng, chỉ cần sử dụng thuật toán của Joey", nhưng theo bất kỳ biện pháp thực tiễn nào, câu trả lời là "bạn không có cơ hội". Như đã được khuyến cáo bởi rwong, bạn nên sử dụng thuật toán nén hạng nặng.