कोल्मोगोरोव जटिलता अनुमान एल्गोरिदम

Question

मैं एक एल्गोरिदम की तलाश में हूं जो दिए गए इनपुट स्ट्रिंग की कोल्मोगोरोव जटिलता के अनुमान को गणना कर सकता है। तो अगर के स्ट्रिंग एस की कोल्मोगोरोव जटिलता है, और टी समय का प्रतिनिधित्व करता है, तो फ़ंक्शन इस तरह कुछ व्यवहार करेगा .. सीमा (टी-> inf) [K_approx (टी, एस)] = के।

Answer 1

इन सिद्धांत, एक प्रोग्राम अपनी इनपुट स्ट्रिंग की कोल्मोगोरोव जटिलता पर अभिसरण कर सकता है क्योंकि चलने का समय अनंतता तक पहुंचता है। यह समानांतर में हर संभव प्रोग्राम को चलाकर काम कर सकता है जो इनपुट स्ट्रिंग या कम की लंबाई है। जब किसी दिए गए लंबाई का कोई प्रोग्राम पाया जाता है, तो उस लंबाई को अब के लिए ज्ञात न्यूनतम लंबाई के रूप में पहचाना जाता है, मुद्रित किया जाता है, और कोई और प्रोग्राम> = लंबाई की कोशिश नहीं की जाती है। यह एल्गोरिदम (सबसे अधिक संभावना) हमेशा के लिए दौड़ता है, छोटे और छोटे लंबाई को प्रिंट करता है, सटीक कोल्मोगोरोव जटिलता को अनंत समय पर परिवर्तित करता है।

बेशक, कार्यक्रमों की घातीय संख्या चलाना बेहद अचूक है। एक अधिक कुशल एल्गोरिदम code golf on StackOverflow पोस्ट करना है। कुछ कमियां:

• अच्छे परिणाम मिलने से कुछ दिन पहले लग सकते हैं।
• यह उत्पादकता हानि में हजारों डॉलर की लागत वाले हमारे सबसे मूल्यवान कंप्यूटिंग संसाधनों की विशाल मात्रा का उपयोग करता है।
• परिणाम समय के साथ कम आवृत्ति के साथ उत्पादित होते हैं क्योंकि संसाधन othercomputations पर जाते हैं।
• कई इनपुट के लिए एल्गोरिदम terminatesprematurely, जिसका अर्थ है कि यह सामान्य रूप से काम नहीं करता है।

Answer 2

मुझे लगता है कि यह काम कर सकता है? अगर किसी को कोई त्रुटि दिखाई देती है, तो कृपया इसे इंगित करें।

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

wikipedia page Kolmogorov जटिलता के लिए एक उपधारा जिसका शीर्षक था "Kolmogorov जटिलता के Incomputability", "बुनियादी परिणाम" अनुभाग के तहत है। यह एक बुनियादी उपाय नहीं है जिसका आप गणना कर सकते हैं, या यहां तक ​​कि उत्पादक अनुमान लगा सकते हैं।

संदेह के बिना, जो भी आप चाहते हैं उसे प्राप्त करने के बेहतर तरीके हैं। यदि आप जो चाहते हैं वह यादृच्छिकता का एक उपाय है, तो आप बाइनरी एंट्रॉपी फ़ंक्शन का प्रयास कर सकते हैं। मानक एल्गोरिदम में से एक द्वारा संपीड़न बिल को भी फिट कर सकता है।

Answer 4

ऐसा लगता है कि रे सोलोमोनोफ इस क्षेत्र में बहुत काम किया है।

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

पहला मुद्दा है कि मैं ध्यान दें कि "Kolmogorov जटिलता" अच्छी तरह से परिभाषित नहीं है। यह कार्यक्रमों का प्रतिनिधित्व करने के तरीके पर कुछ डिग्री पर निर्भर करता है। तो, सबसे पहले आपको जो करना होगा, वह कार्यक्रमों के कुछ एन्कोडिंग को ठीक करेगा (उदाहरण के लिए, जॉय एडम्स का विनिर्देश कि कार्यक्रम जे में लिखे गए हैं)।

एक बार जब आप एन्कोडिंग हो तो एल्गोरिथ्म आप देख रहे हैं काफी सरल है। इसके लिए जॉय का जवाब देखें।

लेकिन स्थिति तेजी से कई कार्यक्रमों को चलाने के लिए होने से भी बदतर है। उन कार्यक्रमों में से प्रत्येक के रूप में लंबे चलाने के रूप में आप संभवतः कल्पना कर सकता सकता है (तकनीकी रूप से: के रूप में एक समारोह इनपुट आकार किसी भी पुनरावर्ती क्रिया की तुलना में तेजी से बढ़ने सकता है समय से चल रहा है)।और भी, यह मामला हो सकता है कि कुछ सबसे छोटे कार्यक्रम सबसे लंबे समय तक चलने वाले हैं। इसलिए जब समानांतर दृष्टिकोण सही मूल्य तक पहुंच जाएगा, क्योंकि समय अनंतता तक जाता है, तो यह धीरे-धीरे धीरे-धीरे करेगा।

आप कार्यक्रम को समय-समय पर रोक सकते हैं, यह समझते हुए कि उस बिंदु पर अनुमान पर्याप्त है। हालांकि, आपको सामान्य रूप से कोई जानकारी नहीं है कि अनुमान कितना अच्छा है। वास्तव में, ऐसे प्रमेय हैं जो दिखाते हैं कि आप कभी नहीं जानते।

तो संक्षिप्त उत्तर "आसान है, बस जॉय के एल्गोरिदम का उपयोग करें", लेकिन व्यावहारिकता के किसी भी उपाय से, जवाब है, "आपके पास कोई मौका नहीं है"। जैसा कि र्वॉन्ग द्वारा अनुशंसित किया गया है, आप केवल एक भारी ड्यूटी संपीड़न एल्गोरिदम का उपयोग कर बेहतर हैं।