Vergleich der Komplexität der Kolmogorov-Theorien

14

Chaitins Unvollständigkeitssatz besagt, dass keine hinreichend starke Theorie der Arithmetik beweisen kann, K(s)>Lwobei K(s) die Kolmogorov-Komplexität der Zeichenkette und eine hinreichend große Konstante ist. ist ausreichend groß, wenn es größer ist als die Größe in Bits einer Prüfmaschine (PCM). Ein PCM für Theorie T verwendet eine als Ganzzahl codierte Zeichenfolge als Eingabe und gibt eine 1 aus, wenn die Zeichenfolge ein gültiger Beweis in der Sprache von T ist .L LsLLTT

Es sei angenommen , dass L(T)>|PCMT|für Theorie T ist eine obere für die Komplexität der gebundenen T . Betrachten Sie die folgende Theorienhierarchie: Die Basistheorie sei Robinson-Arithmetik ( Q ). Augmentiere Q mit zunehmend stärkeren Axiomen der polynombedingten Induktion. Sei Q die mit Q und einem dieser beschränkten Induktionsaxiome beweisbare Theorie der Theoreme . Angenommen, wir können L(Q) und durch Definieren von PCMs für jede Theorie.L(Q)

Ich möchte einen EPCM (Enhanced Proof Checking Machine) für in Betracht ziehen . Diese EPCM nimmt einen String als Eingabe wie ein ECM und hat einen zweiten Eingang, der den Rang und die Ebene einer Untertheorie definiert Q * . Wenn die Eingabezeichenfolge in Q ein gültiger Beweis ist, durchläuft das EPCM die Schritte des Beweises, um den höchsten Rang und die höchste verwendete Induktionsstufe zu bestimmen. Dieser EPCM schreibt dann eine 1, wenn der Eingabesatz ein gültiger Beweis in der angegebenen Untertheorie von Q ∗ ist .QQQQ

Ist der von mir beschriebene Enhanced Proof Checker machbar? Wenn ja, wäre die Größe dieses EPCM nicht nur eine Obergrenze für die Komplexität von , sondern auch eine Obergrenze für die Komplexität einer Subtheorie von Q ?QQ

Ist es vernünftig zu sagen, dass es eine konstante Obergrenze für die Komplexität von und all seinen Untertheorien gibt?Q


Diese Frage wurde von Nelsons fehlgeschlagenem Beweis für die Inkonsistenz der Arithmetik gestellt. Ich habe das vorher nicht erwähnt, weil manche Leute diesen Beweis als störend empfinden. Meine Motivation ist es, eine interessante Frage zu stellen. CSTheory scheint das richtige Forum für diese Frage zu sein. Die Komplexität von und all seinen Untertheorien ist entweder durch eine Konstante begrenzt oder unbegrenzt. Jede Antwort führt zu weiteren Fragen.Q

Wenn die Komplexität der Unter Theorien unbegrenzt ist , können wir Fragen wie fragen , was ist das schwächste Unter Theorie von komplexer als Q * ? Oder komplexer als PA und ZFC? Das Nachdenken über diese Frage hat mir bereits gezeigt, dass es eine strenge Grenze dafür gibt, wie viel eine Theorie über die Komplexität von Kolmogorov-Strings beweisen kann. Wenn Q konsistent ist, kann keine seiner Untertheorien K ( s ) > L ( Q ) für eine beliebige Zeichenkette beweisen . Dies bedeutet, dass selbst wirklich starke Untertheorien nicht beweisen können, dass es komplexere Zeichenfolgen gibt als eine viel schwächere Untertheorie, bei der die schwächere Theorie komplexer ist als QQQQK(s)>L(Q) .Q

Russell Easterly
quelle
1
Dies ist zwar richtig, aber natürlich ist die zusätzliche Eingabe (z . B. ), die zum Überprüfen der Einschränkung des Induktionsschemas erforderlich ist, selbst von unbegrenzter Komplexität, sodass es etwas irreführend ist, anzunehmen, dass Sie diese Komplexität einheitlich begrenzt haben . n
Die zusätzliche Komplexität wäre . Wenn ich n L benötige, müsste ich nur L > c + l o g ( L ) zeigen . log(n)nLL>c+log(L)
Russell Easterly
Ihre Notation erinnert mich etwas verstörend an diesen falschen Versuch, die Inkonsistenz der Arithmetik zu beweisen. Können Sie Ihre Beweggründe klären?
Cody
Hallo Russell. Das klingt für mich ziemlich interessant. Wenn Sie sich jemals unterhalten möchten, lassen Sie es mich bitte wissen. Einen schönen Tag noch! :)
Michael Wehar
Ja, ein solches TM kann verwendet werden, um die Komplexität einer Theorie zu definieren. Ich frage, ob es eine Grenze für die Größe dieses TM gibt, wenn wir mehrere Theorien haben.
Russell Easterly

Antworten:

5

Ich werde versuchen, eine Antwort auf diese Frage zu geben und einige Unklarheiten hinsichtlich der genauen Form der Frage zu beseitigen.

Der erste Punkt , den ich machen will: die in der Mitteilung der Chaitinsche Konstante ist in der Tat eine Funktion von T . Im absoluten Sinne ist es monoton in der Aussagekraft von T : Wenn L ( T ) die kleinste natürliche Zahl ist, für die T K ( s ) L ( T ) für eine beliebige Zeichenkette s ist , dann ist T ' eine konsistente Theorie stärker als T ( T φ impliziert T LTTL(T)

TK(s)L(T)
sTTTφ für einen beliebigen arithmetischen Satz φ ) dann L ( T ) L ( T ) . Das Argument ist sehr einfach: Wenn es gibt s , so dass T K ( s ) L dann T 'K ( s ) L durch Hypothese.TφφL(T)L(T)sTK(s)LTK(s)L

Dies gilt jedoch nur, wenn die absolute Chaitin-Konstante ist. Insbesondere dann , wenn T ' beweist C o n ( T ) , dann T 'L s T K ( ¯ s ) ¯ LL(T)TCon(T)

TLs TK(s¯)L¯

durch Verinnerlichung Chaitins Argument. Jedoch wird ein Beton , für diel

Ts TK(s¯)l¯

wird im Allgemeinen nicht gleich L(T) . Insbesondere kann es viel größer ist , in der Regel proportional zu der Größe des Beweises von in T 'Con(T)T . Dies kann leicht im Beweis des Satzes selbst gesehen werden, der entscheidend von der Konsistenz von abhängt .T

So , während Konsistenz des Systems mit beschränkter Induktion nachweisen kann, die Länge dieser Beweise wird immer länger , je näher Sie bekommen Q * in Ausdruckskraft (eine Möglichkeit , die Unvollständigkeitssätze zu verstehen ist , dass die Länge unendlich wird , wenn Sie erreichen Q * , es gibt also keinen endlichen Konsistenzbeweis in Q selbst). Dies gilt auch für die verschiedenen Obergrenzen der internen L ( T ) s, die Q für jede Untertheorie beschreiben kann.QQQQ L(T)Q

Hier ist die kurze Antwort auf Ihre Frage: ist für alle Untertheorien von Q einheitlich begrenzt , aber Q selbst kann nicht zeigen, dass diese Grenze für alle derartigen Untertheorien gilt. Dies war der entscheidende Fehler, den Nelson (unter mehreren Ebenen des Formalismus begraben) begangen hatte und auf den Tao hier hinwies .L(T)QQ

Cody
quelle
Con(Q)Q
LPRACon(Q)TQPRACon(Q)Con(T), and so it is not hard to show that the bound for Q also works for T (within PRA).
cody
By any sub-theory of Q I of course meant any sub-theory which can be proven to be so in PRA.
cody
Hey Cody, thanks for the answer. Hope all is well. :)
Michael Wehar
1
Thanks Mike! This was a fun question. The fact Nelson himself got confused in the details suggests that there are some subtle pitfalls along the way...
cody