Czy nie możemy przedstawić złożoności Kołmogorowa?

28

Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga U która na wejściu (T,x) (zakodowana jako kod bez prefiksu T a następnie x ) wyprowadza dowolne T na wejściu x (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla x , K(x) , jako długość najkrótszego programu p tak aby U(p)=x .

Czy istnieje maszyna Turinga T , która dla każdego wejścia x wyprowadza liczbę całkowitą T(x)|x|to różni się od złożoności Kołmogorowa dla x , tj. T(x)K(x) ale lim inf|x|T(x)= ?

Warunki są konieczne, ponieważ

(a) jeśli T(x)|x|, wówczas łatwo byłoby wypisać liczbę, która jest trywialnie różna od K(x) ponieważ jest większa niż |x|+cU ,

(b) jeśli lim inf|x|T(x)<C jest dozwolone, wówczas możemy po prostu wyprowadzić 0 (lub inną stałą) dla prawie wszystkich liczb, „na szczęście” zgadując co najwyżej jeden (skończenie wiele liczb), które oceniają na 0 (na inną stałą) i generują tam coś innego. Możemy nawet zagwarantować lim sup|x|T(x)= , wypisując coś w rodzaju 2logn dla x=2n .

Zauważ też, że nasza praca byłaby łatwa, gdybyśmy wiedzieli, że T(x) nie jest przesadny, ale niewiele wiadomo na ten temat, więc odpowiedź może zależeć od U , 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 .

domotorp
źródło
5
Zależy to od twojego kodowania, ponieważ jak wspomniano w temacie o podejrzliwości , do którego linkujesz , może się zdarzyć, że poprawne będą tylko programy o parzystej długości. Aby twoje pytanie było nietrywialne, musisz mieć więcej hipotez dotyczących kodowania. Kp
Denis,
2
Na twoje drugie pytanie: tak. Biorąc pod uwagę liczbę całkowitą , niech oznacza maszynę Turinga. Funkcja nierekurencyjna po przekątnej (lub DNR) jest funkcją taką że dla wszystkich liczb całkowitych , . (To znaczy, jeśli zatrzymuje się na , to , a w przeciwnym razie może być dowolne.) Zostały one dość niedawno zbadane w obliczalności / obliczalności społeczność losowości. Google „po przekątnej nierekurencyjny”, aby znaleźć dokumenty na ten temat. M[M]Mf:NNM[M](M)f(M)[M]Mf(M)[M](M)f(M)
Joshua Grochow
1
@Denis: Myślę, że się mylisz. Zgodnie z moją definicją uniwersalnych maszyn Turinga podaną w pierwszym akapicie wszystkie długości mogą być poprawnymi programami.
domotorp
3
Kilka razy temu pomyślałem (na próżno) o pozornie prostszej wersji: (dis) udowadniając, że dla wystarczająco dużych , dla wszystkich . x0K(x)|x|/2xx0
Marzio De Biasi
1
@Ricky: W porządku, nie mam żadnych ograniczeń w kodowaniu maszyn Turinga, tylko w programach, które można przeczytać w pierwszym akapicie.
domotorp 27.04.2015

Odpowiedzi:

7

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}N0T(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ż inb0n<2bK(n)bbnb|{T(x)=b}|2bTxnthT(x)=bc1K(x)>bc1K(n)bnmoż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.xc2K(x)<b+c2K(n)bxn|K(x)T(x)|<c1+c2b2bx

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!cZT(x)=K(x)+c

Dan Brumleve
źródło
1
Fajnie, myślę, że to powinno zadziałać. Oczywiście nie może być żadnych ciągów z , więc może chcesz wymagać , prawda? f(x)=bf(x)b
domotorp
1
Musi być , aby można było obliczyć z . Myślę, że trzeba wybrać , aby lub mniej więcej łańcuchy były do ​​niego mapowane. Przypuszczalnie założenia powinny sugerować, że istnieje nieskończenie wiele takich (choć w tej chwili tego nie widzę). (O ile mi wiadomo, założenia nie zostały wykorzystane w żaden inny sposób.)f(x)=bnxb,n b2b+1b
Emil Jeřábek popiera Monikę
1
Tak, rzeczywiście jest to potrzebne. Ale dowód jest łatwy dzięki sprzeczności - jeśli zawsze jest jeśli , to patrząc na dowolny zakres , możemy stwierdzić, że przynajmniej ciągi są odwzorowane na , a więc nieskończenie wiele, co jest sprzeczne z . <2bb>b0b0<bBBb0b0lim inf=
domotorp
To, o czym mówi Denis, nie dotyczy sposobu, w jaki zdefiniowałem uniwersalność w pierwszej linii mojego pytania. Jego uwaga jest również trywialna, nie mam pojęcia, dlaczego tak wiele osób głosowało za jego komentarzem. Ale niestety, także błędna odpowiedź Piotra otrzymała tyle głosów poparcia, że ​​tracę wiarę w tę stronę ...
domotorp
Nie ma znaczenia, w jaki sposób kodowane są bazy TM, o ile spełnione są moje kryteria dotyczące uniwersalnej bazy TM, więc komentarz Denisa jest niepoprawny. Gdyby zostało to stwierdzone jako uwaga na temat innego modelu, byłoby to coś innego. W każdym razie, zamiast wycierać nad tym, spróbujmy sprawdzić, czy możemy wzmocnić twój pomysł ...
domotorp
3

Myślę, że następujące prace. Użyję dla złożoności KołmogorowaC(x)

  • Podaj ograniczenie czasowe (powiedzmy, jakąś funkcję wykładniczą długości programu wejściowego) i wywołaj wynik . Jeśli program przekroczy limit czasu, wejdzie w nieskończoną pętlę.UtUtUt
  • Niech będzie najkrótszym programem dla on . Zauważ, że jest obliczalny.Ct(x)xtCt
  • Niech zwróci , chyba że ta wartość jest równaw takim przypadku zwróć 0. O ile nie jest wyjściem pustego programu, w takim przypadku zwróć 1.T(x)Ct(x)+1|x|x
  • Ponieważ , zawsze będzie różnić się od . Logika z poprzedniego kroku zajmuje się przypadkami krawędzi.C(x)Ct(x)T(x)C(x)
  • Ut działa jak kod dla wszystkich łańcuchów, więc ma ograniczoną nieskończoność.
Piotr
źródło
kilka komentarzy, teoria KC w alternatywnej (ale równoważnej) interpretacji stwierdza, że: Prawie wszystkie ciągi są już w optymalnej reprezentacji ( wrt do danego modelu), z wyjątkiem wielu znaczących ciągów, które można przekształcić w optymalną reprezentację (minimum) wrt do danego modelu obliczeniowego (lub TM). W tym sensie, prawie każdy program generuje optymalne reprezentacje ciąg, ale te nie są znane (lub obliczalny) a-priori
Nikos M.
Dlaczego będziesz miał? T(x)|x|
domotorp
@domotorp Technicznie mamy gdzie jest długością najkrótszego programu do drukowania. Oczywiście, ta stała jest również dostępna dla (i tak naprawdę, chyba że program drukowania jest naprawdę wolny, to ta sama stała). T(x)|x|+ccC(x)
Peter
Ale to sprawia, że ​​całe pytanie jest interesujące! Mógłbym poprosić o dowolną funkcję zamiast, np. , moim jedynym celem było wyeliminowanie rozwiązań podobnych do twojego. |x||x|/2+99
domotorp
@domotrop Rozumiem, więc chcesz zmusić aby nie był górną granicą do . To jest bardziej interesujące ...T(x)C(x)
Peter