In der Mathematik ist eine normale Zahl eine reelle Zahl, deren unendliche Folge von Ziffern in jeder Basis gleichförmig im Sinn verteilt wird, dass jeder der Ziffer-Werte dieselbe natürliche Dichte 1 / hat, sind auch alle möglichen Paare von Ziffern mit der Dichte, allen Drillingen von Ziffern ebenso wahrscheinlich mit der Dichte usw. ebenso wahrscheinlich.

Während ein allgemeiner Beweis sein kann vorausgesetzt, dass fast alle Zahlen normal sind (im Sinn, dass der Satz von Ausnahmen Lebesgue Null messen lässt), ist dieser Beweis nicht konstruktiv, und, wie man gezeigt hat, sind nur sehr wenige spezifische Zahlen normal gewesen. Zum Beispiel wird es weit geglaubt, dass die Zahlen 2, π, und e normal sind, aber ein Beweis bleibt schwer erfassbar.

Definitionen

Lassen Sie Σ ein begrenztes Alphabet von b Ziffern und Σ der Satz aller Folgen sein, die von diesem Alphabet gezogen werden können. Lassen Sie S, w  Σ zwei solche Folgen sein, von denen der Letztere begrenzte Schnur ist, die vom Alphabet Σ gezogen ist. Lassen Sie n eine positive ganze Zahl sein. Definieren Sie N (w, n), um die Zahl von Zeiten zu sein, die Schnur w erscheint als eine Teilkette in den ersten n Ziffern der Folge S. (Zum Beispiel, wenn S = 01010101..., dann N (010, 8) = 3.) S ist wenn, für alle begrenzten Schnuren w  Σ, normal

:

(wo | w | die Länge der Schnur w anzeigt; sieh auch Grenze.)

Mit anderen Worten ist S normal, wenn alle Schnuren der gleichen Länge mit der gleichen asymptotischen Frequenz vorkommen. Zum Beispiel, in einer normalen binären Folge (eine Folge über das Alphabet {0,1}), 0 und 1 kommt jeder mit der Frequenz  vor; 00, 01, 10, und 11 kommt jeder mit der Frequenz  vor; 000, 001, 010, 011, 100, 101, 110, und 111 kommt jeder mit der Frequenz  usw. vor. Grob sprechend, ist die Wahrscheinlichkeit, die Schnur w in jeder gegebenen Position in S zu finden, genau, der erwartet hat, ob die Folge aufs Geratewohl erzeugt worden war.

Denken Sie, jetzt wo b eine ganze Zahl ist, die größer ist als 1, und x eine reelle Zahl ist. Denken Sie die unendliche Ziffer-Folge-Vergrößerung S x in der Basis b Stellungszahl-System (wir ignorieren den dezimalen Punkt). Wir sagen, dass x in der Basis b normal ist, wenn die Folge S normal ist. Die Nummer x wird eine normale Zahl genannt (oder manchmal eine absolut normale Zahl), wenn es in der Basis b für jede ganze Zahl b größer normal ist als 1.

Eine gegebene unendliche Folge ist entweder normal oder nicht normal, wohingegen eine reelle Zahl, eine verschiedene Grund-B-Vergrößerung für jede ganze Zahl b  2 habend, in einer Basis, aber nicht in einem anderen (Cassels 1959 und Schmidt 1960) normal sein kann. Alle normalen Zahlen in der Basis r sind in der Basis s normal, wenn, und nur wenn Klotz r / s loggt, eine rationale Zahl (Schmidt 1960) ist.

Eine abtrennende Folge ist eine Folge, in der jede begrenzte Schnur erscheint. Eine normale Folge ist abtrennend, aber eine abtrennende Folge braucht nicht normal zu sein. Eine Zahl, die zu jeder Basis abtrennend ist, wird absolut abtrennend genannt oder wird gesagt, ein Lexikon (Calude und Zamfirescu, 1999) zu sein. Ein Lexikon enthält alle Schriften, die gewesen sind oder jemals auf jeder möglichen Sprache geschrieben werden. Jede normale Zahl ist b-dense, aber nicht notwendigerweise umgekehrt. Ein Satz wird "restlich" genannt, wenn er die Kreuzung einer zählbaren Familie von offenen dichten Sätzen enthält. Der Satz von absolut abtrennendem reals (Lexika) ist ein restlicher (Calude und Zamfirescu, 1999).

Ein anderes schwächeres Eigentum als Normalität ist einfache Normalität. Eine Zahl ist einfach in der Basis b normal, wenn jede individuelle Ziffer mit der Frequenz 1/b erscheint. Für eine gegebene Basis b kann eine Zahl einfach normal (aber nicht normal oder b-dense), b-dense (aber einfach nicht normal oder normal), normal (und so einfach normal sein und b-dense), oder keiner von diesen.

Eigenschaften und Beispiele

Das Konzept einer normalen Zahl wurde von Émile Borel 1909 eingeführt. Mit dem Lemma von Borel-Cantelli hat er den normalen Zahl-Lehrsatz bewiesen: Fast alle reellen Zahlen sind im Sinn normal, dass der Satz von nichtnormalen Zahlen Lebesgue Null (Borel 1909) messen lässt. Dieser Lehrsatz hat die Existenz von normalen Zahlen gegründet. 1917 hat Waclaw Sierpinski gezeigt, dass es möglich ist, eine Einzelheit solche Zahl anzugeben. Becker und Figueira haben 2002 bewiesen, dass es eine berechenbare normale Zahl gibt.

Der Satz von nichtnormalen Zahlen, obwohl "klein", im Sinne, eine Nullmenge zu sein, ist "groß" im Sinne, unzählbar zu sein. Zum Beispiel gibt es unzählbar viele Zahlen, deren dezimale Vergrößerung die Ziffer 5 nicht enthält, und keiner von diesen normal ist.

Die Zahl von Champernowne

:0.1234567891011121314151617...

erhalten durch das Verketten der Dezimaldarstellungen der natürlichen Zahlen in der Ordnung, ist in der Basis 10 normal, aber es könnte in einigen anderen Basen nicht normal sein.

Der Copeland-Erdős unveränderlicher

:0.235711131719232931374143...

erhalten durch das Verketten der Primzahlen in der Basis 10, ist in der Basis 10, wie bewiesen, durch Copeland und Erdős (1946) normal. Mehr allgemein haben die letzten Autoren bewiesen, dass die reelle Zahl in der Basis b durch die Verkettung vertreten

hat

: 0.f (1) f (2) f (3)...,

wo f (n) die n Blüte ist, die in der Basis b ausgedrückt ist, ist in der Basis b normal. Besicovitch (1935) hat dass die Zahl bewiesen, die durch denselben Ausdruck, mit f (n) = n, vertreten ist

:0.149162536496481100121144...

erhalten durch das Verketten der Quadratzahlen in der Basis 10, ist in der Basis 10 normal. Davenport & Erdős (1952) hat bewiesen, dass die Zahl, die durch denselben Ausdruck mit f vertreten ist, der jedes Polynom ist, dessen Werte auf den positiven ganzen Zahlen positive ganze Zahlen sind, die in der Basis 10 ausgedrückt sind, in der Basis 10 normal ist.

Nakai & Shiokawa (1992) hat das bewiesen, wenn f (x) ein nichtunveränderliches Polynom mit echtem solchem coecients dass f (x)> 0 für den ganzen x> 0, dann die reelle Zahl ist, die durch die Verkettung vertreten ist

:0. [f (1)] [f (2)] [f (3)]...,

wo [f (n)] der Teil der ganzen Zahl von f (n) ausgedrückt in der Basis b ist, ist in der Basis b normal. (Dieses Ergebnis schließt als spezielle Fälle alle oben erwähnten Ergebnisse von Champernowne, Besicovitch und Davenport & Erdős ein.) Zeigen die Autoren auch, dass dasselbe Ergebnis noch mehr allgemein hält, wenn f jede Funktion der Form ist

: f (x) = α\· x + α\· x +... + α\· x,

wo der α's und β's reelle Zahlen mit β> β> β>...> β  0, und f (x)> 0 für den ganzen x> 0 sind.

Die Konstante jedes Chaitins ist eine normale Zahl (Calude, 1994).

Eine berechenbare normale Zahl wurde in (Becher 2002) gebaut. Obwohl diese Aufbauten die Ziffern der Zahlen gebaut, die zweiten Shows nicht direkt geben, dass es im Prinzip möglich ist, alle Ziffern einer besonderen normalen Zahl aufzuzählen.

Keine rationale Zahl ist zu jeder Basis normal, da die Ziffer-Folgen von rationalen Zahlen schließlich periodisch sind.

Bailey und Crandall zeigen eine ausführliche unzählbar unendliche Klasse von b-normal Zahlen durch das Stören von Zahlen von Stoneham.

Es ist eine schwer erfassbare Absicht gewesen, die Normalität von Zahlen zu beweisen, die zum Zweck nicht ausführlich gebaut wurden. Es ist zum Beispiel unbekannt, ob 2, π, ln (2) oder e normal ist (aber sie alle werden stark vermutet, um, wegen einiger empirischer Beweise normal zu sein). Es ist nicht sogar bekannt, ob alle Ziffern ungeheuer häufig in den dezimalen Vergrößerungen jener Konstanten vorkommen. Es ist vermutet worden, dass jede vernunftwidrige algebraische Zahl normal ist; während keine Gegenbeispiele bekannt sind, dort auch besteht keine algebraische Zahl, die, wie man bewiesen hat, in jeder Basis normal gewesen ist.

Zusätzliche Eigenschaften von normalen Zahlen schließen ein:

• Jede positive Zahl x ist das Produkt von zwei normalen Zahlen. Zum Beispiel, wenn y gleichförmig aufs Geratewohl aus dem Zwischenraum (0,1) dann fast sicher y gewählt wird und x/y sowohl normal sind, als auch ihr Produkt x ist.
• Wenn x in der Basis b normal ist und q  0 eine rationale Zahl ist, dann in der Basis b normal ist. (Wand 1949)
• Wenn dicht ist (für jeden

• Eine Folge ist normal, wenn, und nur wenn jeder Block der gleichen Länge mit der gleichen Frequenz erscheint. (Ein Block der Länge k ist eine Teilkette der Länge k, an einer Position in der Folge erscheinend, die ein Vielfache von k ist: Z.B ist der erste Block der Länge-k in S S [1.. k] ist der zweite Block der Länge-k S [k+1.. 2k], usw.) Das war in der Arbeit von Ziv und Lempel (1978) implizit und hat ausführlich in der Arbeit von Bourke, Hitchcock und Vinodchandran (2005) gemacht.
• Eine Zahl ist in der Basis b normal, wenn, und nur wenn es einfach in der Basis b für jede ganze Zahl normal ist. Das folgt aus der vorherigen Block-Charakterisierung der Normalität: Da der n Block der Länge k in seiner Basis b Vergrößerung der n Ziffer in seiner Basis b Vergrößerung entspricht, ist eine Zahl einfach in der Basis b normal, wenn, und nur wenn Blöcke der Länge k in seiner Basis b Vergrößerung mit der gleichen Frequenz erscheinen.
• Eine Zahl ist normal, wenn, und nur wenn es einfach in jeder Basis normal ist. Das folgt aus der vorherigen Charakterisierung der Basis b Normalität.
• Eine Zahl ist b-normal, wenn, und nur wenn dort eine Reihe positiver ganzer Zahlen besteht

• Der Satz von normalen Folgen wird unter begrenzten Schwankungen geschlossen: Das Hinzufügen, Entfernen oder Ändern einer begrenzten Zahl von Ziffern in jeder normalen Folge verlassen es normal.

Verbindung zu Zustandsmaschinen

Agafonov hat eine frühe Verbindung zwischen Zustandsmaschinen und normalen Folgen gezeigt: Jede Subfolge, die von einer normalen Folge durch eine regelmäßige Sprache ausgewählt ist, ist auch normal. Mit anderen Worten, wenn man eine Zustandsmaschine auf einer normalen Folge führt, wo jeder der Zustandsmaschinenstaaten entweder "Produktion" oder "keine Produktion" etikettiert wird, und die Maschinenproduktionen die Ziffer es als nächstes nach dem Eingehen in einen "Produktions"-Staat liest, aber nicht Produktion die folgende Ziffer nach dem Eingehen in "keinen Produktionsstaat tut" dann wird die Folge es Produktionen (Agafonov 1968) normal sein.

Eine tiefere Verbindung besteht mit Zustandsspielern (FSGs) und Information lossless Zustandskompressoren (ILFSCs).

:

wo der Betrag des Geldes ist, hat der Spieler d nach dem Lesen der ersten n Ziffern von S (sieh Grenze höher).

:

wo die Zahl der Ziffer-Produktion durch C nach dem Lesen der ersten n Ziffern von S ist. Bemerken Sie, dass das Kompressionsverhältnis (die Grenze, die oben untergeordnet ist), immer zu gleichem 1 durch den 1-Staat-ILFSC gemacht werden kann, der einfach seinen Eingang zur Produktion kopiert.

</ul>

Schnorr und Stimm haben gezeigt, dass kein FSG auf jeder normalen Folge erfolgreich sein kann, und Bourke, Hitchcock und Vinodchandran das gegenteilige gezeigt haben. Deshalb:

:A-Folge ist wenn und nur normal, wenn es keinen Zustandsspieler gibt, der darauf erfolgreich ist.

Ziv und Lempel haben sich gezeigt:

:A-Folge ist normal, wenn, und nur wenn es incompressible durch jede Information lossless Zustandskompressor ist

(sie haben wirklich gezeigt, dass das optimale Kompressionsverhältnis der Folge über den ganzen ILFSCs genau seine Wärmegewicht-Rate, ein quantitatives Maß seiner Abweichung von der Normalität ist, die 1 genau ist, wenn die Folge normal ist). Seit den LZ Kompressionsalgorithmus-Kompressen asymptotisch sowie jedem ILFSC bedeutet das, dass der LZ Kompressionsalgorithmus jede nichtnormale Folge zusammenpressen kann. (Ziv Lempel 1978)

Diese Charakterisierungen von normalen Folgen können interpretiert werden, um dass "normal" = "zufälliger Endzustand" zu bedeuten; d. h. die normalen Folgen sind genau diejenigen, die zufällig zu jeder Zustandsmaschine scheinen. Vergleichen Sie das mit algorithmisch Zufallsfolgen, die jene unendlichen Folgen sind, die zufällig zu jedem Algorithmus scheinen (und haben Sie tatsächlich ähnliche Spiel- und Kompressionscharakterisierungen mit Maschinen von Turing, die Zustandsmaschinen ersetzen).

Verbindung zu equidistributed Folgen

Eine Nummer x ist in der Basis b normal, wenn, und nur wenn die Folge equidistributed modulo 1, oder gleichwertig, mit dem Kriterium von Weyl, wenn und nur wenn ist

:

Referenzen

.......................

Weiterführende Literatur

.

• Wir sind in Ziffern des Pis und Leben Für immer durch Clifford A. Pickover

Siehe auch

• Champernowne unveränderlicher
• Unendlicher Affe-Lehrsatz
• Die Bibliothek Babels

Außenverbindungen