Złożoność Kołmogorowa

Ten artykuł od 2011-11 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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^[1].

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^{[potrzebny przypis]}.

Przypisy

↑ MichałM. Pańczyk MichałM., Wykorzystanie złożoności Kołmogorowa do wyznaczania związków kontekstowych poprzez analizę efektów pracy wyszukiwarek internetowych, Lublin: Uniwersytet Marii Curie-Skłodowskiej, 2008, s. 9 .

[1] MichałM. Pańczyk MichałM., Wykorzystanie złożoności Kołmogorowa do wyznaczania związków kontekstowych poprzez analizę efektów pracy wyszukiwarek internetowych, Lublin: Uniwersytet Marii Curie-Skłodowskiej, 2008, s. 9 .

[1]