Approximation von Folgen durch berechenbare Folgen : eine neue Variante der Chaitin-Kolmogorov-Komplexität

Abstract

Wir betrachten Approximationen unendlicher Folgen durch berechenbare unendliche Folgen minimaler Programmkomplexität. Dieser Zugang zur Charakterisierung zufälliger Folgen hat den Vorteil, dass Einbrüche der Programmkomplexität, wie sie im Falle der Approximation dieser Folgen durch ihre Präfixe gegebener Länge auftreten, nicht vorkommen. Wir erhalten so Klassen zufälliger Folgen, deren Relationen zu den Martin-Löf [M.-L. 66] und Schnorr [Schn. 71] zufälligen Folgen sowie den auf dem Konzept der monotonen Programmkomplexität [Schn. 73], [Lev. 73] behruenden Charakterisierung zufälliger Folgen geklärt wird. Unser Ansatz wird geleitet von der Vorstellung der natürlichen Fortsetzung endlicher Folgen w durch unendliche berechenbare Folgen w.... Wir erweitern auch die Menge der zulässigen Berechnungen, indem wir konvergierende unendliche Berechnungen [Ho. 99] in Betracht ziehen.