Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga która na wejściu (zakodowana jako kod bez prefiksu a następnie ) wyprowadza dowolne na wejściu (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla , , jako długość najkrótszego programu tak aby .
Czy istnieje maszyna Turinga , która dla każdego wejścia wyprowadza liczbę całkowitą to różni się od złożoności Kołmogorowa dla , tj. ale ?
Warunki są konieczne, ponieważ
(a) jeśli , wówczas łatwo byłoby wypisać liczbę, która jest trywialnie różna od ponieważ jest większa niż ,
(b) jeśli jest dozwolone, wówczas możemy po prostu wyprowadzić (lub inną stałą) dla prawie wszystkich liczb, „na szczęście” zgadując co najwyżej jeden (skończenie wiele liczb), które oceniają na (na inną stałą) i generują tam coś innego. Możemy nawet zagwarantować , wypisując coś w rodzaju dla .
Zauważ też, że nasza praca byłaby łatwa, gdybyśmy wiedzieli, że nie jest przesadny, ale niewiele wiadomo na ten temat, więc odpowiedź może zależeć od , choć wątpię, by tak było.
Wiem, że stosunki są badane ogólnie, ale
Czy ktoś kiedykolwiek zadał podobne pytanie, gdzie naszym celem jest podanie algorytmu, który nie wyprowadza jakiegoś parametru?
Moją motywacją jest ten problem http://arxiv.org/abs/1302.1109 .
źródło
Odpowiedzi:
Pytanie można sformułować inaczej, czy , i jak Denis wskazuje w komentarzach jest to fałszywe w przypadku niektórych kodowań. Oto słabsze stwierdzenie i próba jego udowodnienia, która nie zależy od żadnych szczegółów kodowania, ale dla uproszczenia założę język binarny:liminf|x|→∞|T(x)−K(x)|=0
Niech będzie funkcją obliczalną spełniającą i . Następnie . Nieoficjalnie, jeśli istnieje cel wokół złożoności Kołmogorowa dla każdego łańcucha, który rośnie bezgranicznie, żadna funkcja obliczeniowa nie może go uniknąć.T:{0,1}∗→N 0≤T(x)≤|x| liminf|x|→∞T(x)=∞ liminf|x|→∞|T(x)−K(x)|<∞
Aby to zobaczyć, niech będzie losową liczbą bitową, tj. oraz . Dla wszystkich istnieje taki losowy . Należy również zauważyć, że istnieje nieskończona liczba wartości na których , wynika to z warunkami dotyczącymi . Teraz niech będzie najmniejszym ciągiem takim, że . Oczywiście istnieje stała taka, że , ponieważ in b 0≤n<2b K(n)≥b b n b |{T(x)=b}|≥2b T x nth T(x)=b c1 K(x)>b−c1 K(n)≥b n można obliczyć z . I istnieje stała taka, że , ponieważ jest również ograniczona z góry tylko o stałą większą niż , a można obliczyć z . Następnie , i mamy nieskończoną liczbę opcji dla (tych z preimage kardynalności co najmniej ), co daje nieskończoną liczbę wartości dla , więc skończymy.x c2 K(x)<b+c2 K(n) b x n |K(x)−T(x)|<c1+c2 b 2b x
Implikacją jest to, że dla niektórych , nieskończenie często. Można więc powiedzieć, że nie możemy wyjść z czegoś, co nie jest złożonością Kołmogorowa!c∈Z T(x)=K(x)+c
źródło
Myślę, że następujące prace. Użyję dla złożoności KołmogorowaC(x)
źródło