fbpx
Wikipedia

Chaitinsche Konstante

Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält.

Ω {\displaystyle \Omega } ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als

Ω = p h a ¨ l t 2 | p | {\displaystyle \Omega =\sum _{p\ \mathrm {h{\ddot {a}}lt} }2^{-\left|p\right|}}

wobei die Summe über alle haltenden Programme p {\displaystyle p} gemeint ist (alle Programme, die ohne Eingabe nach endlicher Laufzeit halten) und | p | {\displaystyle |p|} die Länge des Programms in Bit bezeichnet. Das bedeutet also, dass jedes haltende Programm der Länge m Bit das m-te Bit der Binärdarstellung von Ω {\displaystyle \Omega } um 1 erhöht.

Bemerkung: Da es gewisse Freiheiten gibt, universelle Turingmaschinen zu definieren, hängt der genaue Wert der Konstante von der gewählten Maschinendefinition ab.

Durch Kenntnis der ersten n Bit der Konstante lässt sich das Halteproblem für bis zu n Bit lange Programme entscheiden, sodass sich durch genaue Kenntnis der ersten paar tausend Bit der Konstante viele interessante Probleme der Mathematik lösen ließen.

Da das Halteproblem aber nicht lösbar ist, kann Ω {\displaystyle \Omega } nicht berechenbar sein und ist also eine transzendente reelle Zahl.

Eine Forschergruppe um Cristian Calude von der Universität Auckland bestimmte im Jahr 2002 durch Überprüfen aller Turingprogramme von bis zu 80 Bit Länge die ersten 64 Bit der Zahl.

chaitinsche, konstante, sprache, beobachten, bearbeiten, chaitinsche, konstante, gibt, wahrscheinlichkeit, eine, universelle, turingmaschine, für, eine, beliebige, eingabe, anhält, displaystyle, omega, beispiel, für, eine, nicht, berechenbare, zahl, nach, greg. Chaitinsche Konstante Sprache Beobachten Bearbeiten Die chaitinsche Konstante gibt die Wahrscheinlichkeit an mit der eine universelle Turingmaschine fur eine beliebige Eingabe anhalt W displaystyle Omega ist ein Beispiel fur eine nicht berechenbare Zahl Sie ist nach Gregory Chaitin definiert als W p h a l t 2 p displaystyle Omega sum p mathrm h ddot a lt 2 left p right wobei die Summe uber alle haltenden Programme p displaystyle p gemeint ist alle Programme die ohne Eingabe nach endlicher Laufzeit halten und p displaystyle p die Lange des Programms in Bit bezeichnet Das bedeutet also dass jedes haltende Programm der Lange m Bit das m te Bit der Binardarstellung von W displaystyle Omega um 1 erhoht Bemerkung Da es gewisse Freiheiten gibt universelle Turingmaschinen zu definieren hangt der genaue Wert der Konstante von der gewahlten Maschinendefinition ab Durch Kenntnis der ersten n Bit der Konstante lasst sich das Halteproblem fur bis zu n Bit lange Programme entscheiden sodass sich durch genaue Kenntnis der ersten paar tausend Bit der Konstante viele interessante Probleme der Mathematik losen liessen Da das Halteproblem aber nicht losbar ist kann W displaystyle Omega nicht berechenbar sein und ist also eine transzendente reelle Zahl Eine Forschergruppe um Cristian Calude von der Universitat Auckland bestimmte im Jahr 2002 durch Uberprufen aller Turingprogramme von bis zu 80 Bit Lange die ersten 64 Bit der Zahl Literatur BearbeitenCristian S Calude Information and Randomness An Algorithmic Perspective 2 Auflage Springer Verlag Berlin 2002 ISBN 3 540 43466 6 Gregory Chaitin A theory of program size formally identical to information theory PDF 249 kB April Dezember 1974 In Journal of the ACM 22 Juli 1975 S 329 340 englisch Weblinks BearbeitenEric W Weisstein Chaitinsche Konstante In MathWorld englisch Cristian S Calude s Website die ersten 64 Bit einer chaitinschen Konstante Jorg Resag Die Grenzen der Berechenbarkeit joerg resag de 2008 Kapitel 3 4 Die seltsamste Zahl Chaitins Omega Erklarvideo von Edmund Weitz auf YouTubeAbgerufen von https de wikipedia org w index php title Chaitinsche Konstante amp oldid 213240706, wikipedia, wiki, deutsches

deutschland

buch, bücher, bibliothek

artikel

lesen, herunterladen

kostenlos

kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele