Kolmogorov-Komplexität mit schwachen Beschreibungssprachen

Wir können uns die Kolmogorov-Komplexität eines Strings $x$ als die Länge des kürzesten Programms $P$ und $y$ so eingeben , dass $x = P(y)$ . Normalerweise werden diese Programme aus einem Turing-Komplett-Set erstellt (wie $P$ die Beschreibung einer Turing-Maschine oder ein Programm in LISP oder C). Selbst wenn wir uns die ressourcenbeschränkte Komplexität von Kolmogorov ansehen, sehen wir uns immer noch Turing-Maschinen an, aber mit einigen Einschränkungen hinsichtlich ihrer Laufzeit oder des Platzbedarfs. Dies hat unter anderem zur Folge, dass die Komplexität einer Zeichenfolge nicht zu entscheiden ist. Dies scheint eine unangenehme Funktion zu sein.

Was passiert, wenn wir vollständige Berechnungsmodelle verwenden, um die Kolmogorov-Komplexität zu definieren?

Wenn wir ein ausreichend restriktives Modell wählen (sagen wir, unser Modell kann nur die Identität implementieren), wird die Komplexität eines Strings entscheidend, obwohl wir auch den Invarianzsatz verlieren. Ist es möglich, ein Modell zu haben, das stark genug ist, um die Komplexität (bis zu einem konstanten Versatz oder sogar einem multiplikativen Faktor) des Turing-complete-Modells zu erreichen, aber schwach genug, um die Komplexität eines Strings dennoch entscheiden zu können? Gibt es einen Standardnamen für die Kolmogorov-Komplexität bei nicht-Turing-vollständigen Berechnungsmodellen? Wo könnte ich mehr darüber lesen?

Nehmen wir an, es gibt eine "entscheidbare" Komplexität sich von der Kolmogorov-Komplexität K ( s ) durch Verschiebung, durch Faktor oder allgemeiner durch eine entscheidbare monotone unbegrenzte numerische Funktion f ( n ) unterscheidet, so dass K ( s ) > f ( D ( s ) ) .$D(s)$$K(s)$$f(n)$$K(s) > f(D(s))$

Als entscheidbar ist, ist es möglich (effektiv) eine Folge von Strings wählen s n , so dass f ( D ( s n ) ) > v f f ( n ) , wo v f f einig „sehr , sehr schnell wächst , ist Funktion "wie exp ( exp ( exp ( n ) ) ) .$D(s)$$s_n$$f(D(s_n))> \mathrm{vff}(n)$$\mathrm{vff}$$\exp(\exp(\exp(n)))$

Nehmen wir an, wir haben , dh die Kolmogorov-Komplexität der Zeichenkette s ( n ) wächst schnell mit n . Der Index n identifiziert jedoch auch die Zeichenfolge s ( n ) und kann daher als Obergrenze von K ( s n ) behandelt werden (mit einer gewissen konstanten Verschiebung). Jede Zahl n braucht nur log ( n $K(s_n) > \mathrm{vff}(n)$$s(n)$$n$$n$$s(n)$$K(s_n)$$n$$\log(n)$Bits, um es darzustellen, und dies steht im Widerspruch zu der schnell wachsenden Komplexität von .$K(s_n)$

Somit für jede monotone entscheidbar unbeschränkte numerische Funktion existiert Strings s so , dass K ( s ) ≯ f ( D ( s ) ) .$f$$s$$K(s) \not> f(D(s))$

Die Unberechenbarkeit von allgemeinem KC ist eine Folge der Unentscheidbarkeit des Stoppproblems in Bezug auf die für KC verwendete Maschinenklasse. Wenn wir das Halteproblem über die Klasse der Maschinen entscheiden können, können wir den KC eines gegebenen Strings gemäß diesen berechnen. Führen Sie einfach alle Maschinen- und Eingabepaare aus, die bis zu dem ersten, der ausgibt, anhalten , und wählen Sie dann das kürzeste aus.$x$