Złożoność Kołmogorowa
Z Wikipedii, wolnej encyclopedia
Złożoność Kołmogorowa – długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.
Ten artykuł od 2011-11 wymaga zweryfikowania podanych informacji. |
Rozwinięcie dziesiętne liczby pi, choć nieskończone, ma bardzo niską złożoność Kołmogorowa, ponieważ istnieje bardzo prosty program, który generuje dowolną liczbę jej cyfr. Złożoność Kołmogorowa jest różna dla różnych komputerów (ściślej – maszyn Turinga lub obiektów izomorficznych z nimi). Ze względu na nierozstrzygalność problemu stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu.