Złożoność Kołmogorowa: Dlaczego potrzebujesz więcej bajtów niż samego łańcucha?

Czytałem wpis Wikipedii o złożoności Kołmogorowa ( dzięki temu pytaniu ), który stwierdza:

Można wykazać, że złożoność Kołmogorowa dowolnego łańcucha nie może być większa niż kilka bajtów więcej niż długość samego łańcucha.

Dlaczego miałbyś kiedykolwiek potrzebować czegoś więcej niż samego łańcucha, aby to opisać?

Dokładna wartość złożoności Kołmogorowa zależy od języka wybranego do reprezentowania łańcuchów. Ten język musi być kompletny Turinga, więc reprezentowanie wszystkich ciągów jako siebie nie jest opcją.

Zgodnie z zasadą szufladki, jeśli istnieje co najmniej jeden ciąg długości co najwyżej którego reprezentacja jest krótsza niż ona sama, wówczas istnieje również co najmniej jeden ciąg długości co najwyżej n, którego reprezentacja jest dłuższa niż ona sama. (Reprezentacja jest algorytmem kompresji).$n$$n$

Możesz mieć język opisu, w którym każdy ciąg ma reprezentację co najwyżej o jeden bit dłuższą niż on sam: każdą reprezentację zacznij od bitu, który wskazuje albo „drukuj dosłownie”, albo „interpretuj”. Jednak nie wszystkie języki opisu są takie proste.

$C$$C$

Omawiany tutaj opis ciągu stanowi dane wejściowe do uniwersalnej maszyny Turinga. Możesz myśleć o tym jak o programie C. Łańcuch hello worldnie przez siebie, tworząc program w C, ale po jednym robi: int main(int argc, char *argv[]) { printf("hello world"); }. Jak widać, narzut jest stały, ale nie zerowy.