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

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) > L$$K(s)$$s$$L$$L$$T$$T$

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) > |PCM_T|$$T$$T$$Q$$Q$$Q^*$$Q$$L(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 ∗ .$Q^*$$Q^*$$Q^*$$Q^*$

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 ∗ ?$Q^*$$Q^*$

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ż $Q^*$$Q^*$$Q^*$$K(s) > L(Q^*)$ .$Q^*$

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 $L$$T$$T$$L(T)$

$$T\not\vdash K(s)\geq L(T)$$ $s$$T'$$T$$T\vdash\varphi$ 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'\vdash\varphi$$\varphi$$L(T')\geq L(T)$$s$$T\vdash K(s)\geq L$$T'\vdash K(s)\geq 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 ) ≥ Ż L$L(T)$$T'$$\mathrm{Con}(T)$

$$T'\vdash \exists L\forall s\ \lceil T\not\vdash K(\overline{s})\geq \overline{L}\rceil$$

internalizując argument Chaitina. Jednakże , A betonu , dla którego$l$

$$T'\vdash\forall s\ \lceil T\not\vdash K(\overline{s})\geq\overline{l}\rceil$$

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 $\mathrm{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.$Q^*$$Q^*$$Q^*$$Q^*$ $L(T)$$Q^*$

$L(T)$$Q^*$$Q^*$