Algorithmische Informationstheorie

Die algorithmische Informationstheorie ist eine Theorie aus der theoretischen Informatik, die im Gegensatz zur klassischen Informationstheorie die Kolmogorow-Komplexität zur Bestimmung des Informationsgehalts verwendet. Sie wurde im Wesentlichen von Gregory Chaitin, Andrey Kolmogorov und Ray Solomonoff entwickelt.

Zur Beschreibung des Informationsgehalts einer Zeichenkette betrachtet die algorithmische Informationstheorie die Größe eines kleinsten Algorithmus, der die Zeichenkette erzeugt. Gregory Chaitin präzisierte diese allgemein als Kolmogorow-Komplexität bekannte Größe durch ein spezielles Maschinenmodell, nach dem der Algorithmus ausführbar sein muss. Wie Chaitin beweisen konnte, lässt sich der algorithmische Informationsgehalt einer Zeichenkette nicht endgültig angeben, da nicht beweisbar ist, ob ein gegebenes Programm zu ihrer Erzeugung wirklich das kürzeste ist. Ebenso wie der Informationsbegriff nach Claude Shannon trifft die algorithmische Informationstheorie keinerlei Aussagen über Bedeutung, Wissen und ähnliche nicht mathematisch definierten Begriffe.

Beispiel

Gemäß der klassischen Definition nach Claude Shannon ist der Informationsgehalt der folgenden binären Folge gleich (gilt nur für Entropie erster Ordnung):

1000110111100101

1111111100000000

Während die erste Folge durch Münzwurf als Zufallsgenerator erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr algorithmische Information, da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter anderem durch Datenkompression) komprimiert werden kann. Zufällige Zahlenfolgen und weißes Rauschen enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.

Mathematischer Hintergrund

Der Ansatz von Andrei Kolmogorow lässt als Algorithmen Programme für beliebige Turingmaschinen zu. Gregory Chaitin setzt die Kolmogorow-Komplexität zur Theorie rekursiver Funktionen (siehe auch µ-Rekursion, Lambda-Kalkül) und dem Werk von Kurt Gödel in Beziehung. Er beschränkt die möglichen Programme auf solche, die selbst wieder auf einer speziellen Variante der universellen Turingmaschine (UTM) laufen, auf der so genannten selbst-limitierenden universellen Turingmaschine.

Gemäß einem Theorem von Chaitin kann allerdings nicht grundsätzlich festgestellt werden, ob eine Zeichenkette algorithmisch weiter verkürzt werden kann. So können beispielsweise neue und effektivere Kompressionsalgorithmen gefunden werden oder eine scheinbar zufällige Zahlenfolge kann von einem Pseudozufallszahlengenerator stammen. Wegen des Halteproblems können auch nicht alle Turingmaschinen, die kleiner als eine gegebene Zeichenfolge sind, in endlicher Zeit durchprobiert werden.

Literatur

Günther Hotz: Algorithmische Informationstheorie. Band 25, Statistische Informationstheorie und Anwendungen auf algorithmische Fragestellungen, B.G. Teubner Verlagsgesellschaft, Stuttgart 1997, ISBN 978-3-8154-2310-3.
Dirk W. Hoffmann: Grenzen der Mathematik. Eine Reise durch die Kerngebiete der mathematischen Logik, 2. Auflage, Springer Verlag, berlin / Heidelberg 2013, ISBN 978-3-642-34719-1.
Lienhard Pagel: Information ist Energie. Definition eines physikalisch begründeten Informationsbegriffes, Springer Fachmedien, Wiesbaden 2013, ISBN 978-3-8348-2611-4, S. 68–70.

Weblinks

Gregory Chaitin: How to Run Algorithmic Information Theory on a Computer. (englisch)
Komprimierte Nachrichten von Aliens mit Rauschen identisch
{{#if: | {{{3}}}: }}{{#if: | {{{2}}} | Artikel}}. In: Scholarpedia. (englisch, inkl. Literaturangaben)
<templatestyles src="Webarchiv/styles.css" />{{#if:20131213010842

      | {{#ifeq: 20131213010842 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20131213010842}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20131213010842}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics | {{#invoke:WLink|getEscapedTitle|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}} | {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20131213010842|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics
    | {{#if: {{#invoke:WLink|isBracketedLink|G. J. Chaitin, IBM Research Division, P. O. Box 704, Yorktown Heights: The Limits of Mathematics}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (abgerufen per Archive org. am 5. Januar 2018)

Über erkenntnistheoretische Implikationen der algorithmischen Informationstheorie (abgerufen am 5. Januar 2018)