Please use this identifier to cite or link to this item:
doi:10.22028/D291-26141
Title: | Approximation von Folgen durch berechenbare Folgen : eine neue Variante der Chaitin-Kolmogorov-Komplexität |
Author(s): | Gärtner, Tobias Hotz, Günter |
Language: | German |
Year of Publication: | 2002 |
OPUS Source: | Saarbrücken, 2000 |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-42112 hdl:20.500.11880/26197 http://dx.doi.org/10.22028/D291-26141 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 2002/01 |
Date of registration: | 7-Sep-2011 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14_2002_01.pdf | 377,83 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.