Porównanie złożoności teorii Kołmogorowa

14

Twierdzenie Chaitina o niekompletności mówi, że żadna wystarczająco silna teoria arytmetyki nie może udowodnić, że gdzie K ( s ) to złożoność Kołmogorowa ciągów s, a L jest wystarczająco dużą stałą. L jest wystarczająco duży, jeśli jest większy niż rozmiar w bitach maszyny sprawdzającej proof (PCM). PCM dla teorii T wykonuje ciąg zakodowany jako całkowitą jako dane wejściowe i wyprowadza wartość 1, jeśli ciąg jest ważny dowód w języku T .K(s)>LK(s)sLLTT

Załóżmy, że dla teorii T jest górną granicą dla złożoności T . Rozważ następującą hierarchię teorii: Niech podstawową teorią będzie arytmetyka Robinsona ( Q ). Augment P z coraz silniejszych axioms wielomianu ograniczonym indukcji. Niech Q będzie teorią twierdzeń, które można udowodnić za pomocą Q i dowolnego z tych ograniczonych aksjomatów indukcyjnych. Załóżmy, że możemy zdefiniować L ( Q ) i L ( Q L(T)>|PCMT|TTQQQQL(Q) poprzez zdefiniowanie PCM dla każdej teorii.L(Q)

Chcę rozważyć ulepszoną maszynę do sprawdzania proofów (EPCM) dla . Ten EPCM przyjmuje ciąg znaków jako dane wejściowe podobnie jak ECM i ma drugie wejście, które określa stopień i poziom pod-teorii Q . Jeżeli ciąg wejściowy jest ważny dowód w Q * EPCM następnie przechodzi przez kolejne etapy dowodu w celu ustalenia najwyższego poziomu indukcji rangę i używane. Ten EPCM zapisuje następnie 1, jeśli zdanie wejściowe jest ważnym dowodem w określonej pod-teorii Q .QQQQ

Czy opisany przeze mnie sprawdzony dowód jest wykonalny? Jeśli tak, to czy wielkość tego EPCM byłaby górną granicą nie tylko dla złożoności , ale także górną granicą złożoności jakiejkolwiek sub-teorii Q ?QQ

Czy rozsądne jest stwierdzenie, że istnieje stała górna granica złożoności i wszystkich jej pod-teorii?Q


Pytanie to zostało zainspirowane przez nieudany dowód Nelsona na niespójność arytmetyki. Nie wspomniałem o tym wcześniej, ponieważ niektórzy uważają ten dowód za niepokojący. Moją motywacją jest zadanie interesującego pytania. Wydaje się, że CSTheory jest właściwym forum dla tego pytania. Złożoność i wszystkich jej pod-teorii jest albo stała, albo nieograniczona. Każda odpowiedź prowadzi do większej liczby pytań.Q

Jeśli złożoność pod-teorii jest nieograniczona, możemy zadawać pytania, jak najsłabsza pod-teoria bardziej złożona niż Q ? Lub bardziej złożony niż PA i ZFC? Myślenie o tym pytaniu pokazało mi już, że istnieje poważna granica tego, jak wiele teorii może udowodnić złożoność łańcuchów Kołmogorowa. Jeśli Q jest spójne, to żadna z jego pod-teorii nie może udowodnić K ( s ) > L ( Q ) dla dowolnego łańcucha. Oznacza to, że nawet bardzo silne pod-teorie nie mogą udowodnić, że istnieją bardziej złożone ciągi niż niektóre znacznie słabsze pod-teorie, w których słabsza teoria jest bardziej złożona niż QQQQK(s)>L(Q) .Q

Russell Easterly
źródło
1
Jest to poprawne, jeśli chodzi o to, ale oczywiście dodatkowe dane wejściowe ( , powiedzmy) wymagane do sprawdzenia ograniczenia schematu indukcyjnego mają samą nieograniczoną złożoność, więc nieco mylące jest sugerowanie, że ograniczyłeś te złożoności równomiernie . n
Dodatkowa złożoność będzie . Gdybym wymagał n L , musiałbym tylko wykazać L > c + l o g ( L ) . log(n)nLL>c+log(L)
Russell Easterly
Twoja notacja nieco niepokojąco przypomina mi niewłaściwą próbę wykazania niespójności arytmetycznej. Czy możesz wyjaśnić swoje motywacje?
cody
Cześć Russell. Brzmi dla mnie całkiem interesująco. Jeśli kiedykolwiek chcesz porozmawiać, daj mi znać. Miłego dnia! :)
Michael Wehar
Tak, taka TM może być użyta do zdefiniowania złożoności teorii. Pytam, czy istnieje ograniczenie wielkości tej bazy TM, gdy mamy wiele teorii.
Russell Wielkanocny

Odpowiedzi:

5

Spróbuję udzielić odpowiedzi na to pytanie i postaram się wyjaśnić pewne zamieszanie co do dokładnej formy pytania.

Pierwszym punktem chcę zrobić: the w zestawieniu stałej Chaitin jest rzeczywiście funkcją T . W sensie absolutnym jest wyrazem monotonicznym w wyrazistości T : jeśli L ( T ) jest najmniejszą liczbą naturalną, dla której T K ( s ) L ( T ) dla dowolnego ciągu s , to jeśli T ' jest spójną teorią silniejszy niż T ( T φ implikuje T LTTL(T)

TK(s)L(T)
sTTTφ dla dowolnego zdania arytmetycznego φ ), a następnie L ( T ) L ( T ) . Argument ten jest bardzo prosta, gdy istnieje y takie, że T K ( a ) L czym T 'K ( a ) L według hipotezy.TφφL(T)L(T)sTK(s)LTK(s)L

Jest to jednak prawdą tylko wtedy, gdy jest absolutną stałą Chaitin. W szczególności, gdy T ' dowodzi C O N ( T ) , a T "L s T K ( Ż a ) Ż LL(T)TCon(T)

TLs TK(s¯)L¯

internalizując argument Chaitina. Jednakże , A betonu , dla któregol

Ts TK(s¯)l¯

na ogół nie będzie równy L(T) . W szczególności może być większe, na ogół proporcjonalne do wielkości dowodu w T "Con(T)T . Można to łatwo zauważyć w dowodzie twierdzenia samego, który w zasadniczy sposób polega na konsystencji .T

Tak więc, chociaż może udowodnić spójność układu z ograniczoną indukcją, długość tych dowodów jest tym większa, im bardziej zbliżasz się do Q w ekspresyjności (jednym ze sposobów zrozumienia twierdzeń o niekompletności jest to, że długość staje się nieskończona, gdy osiągniesz Q , dlatego nie ma skończonego dowodu zgodności w samym Q ). To samo dotyczy różnych górnych granic wewnętrznych L ( T ) s Q ∗, które można opisać dla każdej pod-teorii.QQQQ L(T)Q

L(T)QQ

cody
źródło
Con(Q)Q
LPRACon(Q)TQPRACon(Q)Con(T)QT
Q
Cześć Cody, dzięki za odpowiedź. Mam nadzieję, że wszystko w porządku. :)
Michael Wehar
1
Dzięki Mike! To było zabawne pytanie. Fakt, że sam Nelson pomylił się w szczegółach, sugeruje, że po drodze są pewne subtelne pułapki ...
cody