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.

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.


Witaj

Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.

Źródło

Zawartość tej strony pochodzi stąd.

Odsyłacze

Generator Margonem

Podziel się