Złożoność Kołmogorowa
Z Wikipedii, wolnej encyklopedii
 |
Ten artykuł od 2011-11 wymaga uzupełnienia źródeł podanych informacji. Możliwe, że ten artykuł w całości albo w części zawiera informacje nieprawdziwe. Informacje bez źródeł w każdej chwili mogą zostać zakwestionowane i usunięte. Pomóż Wikipedii i dodaj przypisy do materiałów opublikowanych w wiarygodnych źródłach. |
Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.
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 problem stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu.
