Irrationale Zahlen, die von einem deterministischen zellulären Automaten generiert werden?

Question

Irrationale Zahlen, die von einem deterministischen zellulären Automaten generiert werden?

Mathematik
Zellular-Automaten
irrationale Zahlen

Jurij S

Wenn wir einen einfachen zellularen 1D-Automaten betrachten (der auf eine binäre Zeichenfolge einwirkt) und einen Wert an einer festen Position in der Zeichenfolge aufzeichnen, können wir die aufgezeichnete Sequenz als eine binäre Zahl interpretieren.

Die meisten einfachen deterministischen zellularen Automaten erzeugen periodische Folgen binärer Ziffern, die als rationale Zahlen interpretiert werden können.

Es gibt jedoch „zufällige“ deterministische CA, wie z. B. die elementare CA-Regel 30, die von S. Wolfram entdeckt wurde. Ausgehend von einem einzelnen Punkt generiert es Daten, die zufällig genug sind, um als Zufallszahlengenerator verwendet zu werden. Weitere Informationen finden Sie in diesem Dokument .

Nun, da diese Zertifizierungsstelle perfekt deterministische (und einfache) Regeln hat, was können wir über Zahlen sagen, die sie an festen Zeichenfolgenpositionen generiert?

Da die meiste „Zufälligkeit“ auf der rechten Seite stattfindet, schauen wir uns die Zahlen an, die wir an Positionen von der Mitte nach rechts erhalten, beginnend mit der obersten $1$ jeweils (siehe Abbildung). Alle Zahlen haben null ganzzahlige Teile und werden von binär in die Dezimalschreibweise umgewandelt:

A_{0} = 0,8623897839473840486408002460867511281 \dots

$a_0=0.8623897839473840486408002460867511281\dots$

A_{1} = 0,6619938131535679545367590611375473724 \dots

$a_1=0.6619938131535679545367590611375473724\dots$

A_{2} = 0,7759963493462055882598583123808285092 \dots

$a_2=0.7759963493462055882598583123808285092\dots$

A_{3} = 0,7313593429560050953478343145780694591 \dots

$a_3=0.7313593429560050953478343145780694591\dots$

A_{4} = 0,8215879687059052475349289186091204860 \dots

$a_4=0.8215879687059052475349289186091204860\dots$

A_{5} = 0,6314259431664999548181068438831291123 \dots

$a_5=0.6314259431664999548181068438831291123\dots$

A_{6} = 0,8079966728503828647993510584534608703 \dots

$a_6=0.8079966728503828647993510584534608703\dots$

Können wir beweisen/widerlegen, dass diese Zahlen irrational sind? Transzendental? Oder können wir anhand direkter Experimente nur raten? Was ist mit anderen solchen „zufälligen“ zellularen Automaten?

N74

Wenn Sie keine unendlichen Ziffern haben, ist Ihre Zahl rational. Und man kann nur unendlich viele Ziffern in unendlicher Zeit haben.

Benutzer2469

@ N74 Ja, aber zellulare Automaten wie dieser bleiben für immer bestehen. Das OP hat gerade die ersten paar Schritte gezeigt. Mit jedem neuen Schritt erhalten Sie mehr Ziffern.

Jurij S

@ N74, sagst du, dass es keine irrationalen Zahlen gibt? Niemand war in der Lage, unendliche Ziffern von zu erhalten

π

$\pi$ noch

N74

@YuriyS Ich sage, dass kein deterministischer Prozess eine irrationale Zahl erzeugen kann, es sei denn, er läuft für immer. Denken Sie an das klassische Beispiel der Konstruktion einer irrationalen Zahl:

a_{0} = 0.1

$a_0=0.1$ ,

a_{1} = 0.101

$a_1=0.101$ ,

a_{2} = 0.101001

$a_2=0.101001$ ,

a_{3} = 0.1010010001

$a_3=0.1010010001$ ;

a_{\infty}

$a_{\infty}$ ist doch alles transzendent

a_{n}

$a_n$ rational sind.

N74

@barrycarter Irrationale Zahlen sollten eine zählbare Unendlichkeit von Ziffern haben, lassen Sie den Algorithmus laufen und am Ende des Universums haben Sie eine irrationale Zahl. Keine maschinendarstellbare Zahl ist irrational.

Jurij S

@ N74 sagst du das noch einmal

π

$\pi$ ,

e

$e$ ,

\sqrt{2}

$\sqrt{2}$ , etc, gibt es nicht? Warum kann eine Cauchy-Folge nicht von einem zellularen Automaten (oder einer anderen Maschine) definiert werden?

N74

@YuriyS wegen Zeit und Ressourcen: Keine Maschine hat keine Beschränkung für beide.

Jurij S

@ N74, tut mir leid, könnten Sie bitte Ihre Position zu irrationalen Zahlen im Allgemeinen erläutern? Existieren sie, obwohl wir sie nicht in endlicher Zeit berechnen können?

N74

@YuriyS Sicherlich gibt es Irrationale und wir haben viele Beweise dafür in unserer kontinuierlichen Welt. Das Problem besteht darin, sie in einer Maschine zu generieren ... ohne unendlichen Speicher müssen Sie die Sequenz wiederholen, zuerst oder zuletzt.

Benutzer2469

Können wir zur Lösung dieses Problems sagen, dass wir eine Folge berechenbarer rationaler Zahlen haben, deren Grenzwert gegen eine irrationale Zahl konvergiert?

Jimjim

Der Punkt ist folgender: Kein deterministischer endlicher Automat kann irrationale Zahlen erzeugen.

Jurij S

@Arjang, dann gibt es überhaupt keine Möglichkeit, irrationale Zahlen zu generieren?

Jimjim

@YuriyS: Sicher, nehmen Sie zum Beispiel Binärziffern mit 0,10110011100011110000 ... das ist eine irrationale Zahl, vielleicht sogar transzendental. die Ziffern sind einfach zu generieren, solange sie sich nicht ab einigen Stellen wiederholen.

Jimjim

@YuriyS: Ich habe mir diese Zahl gerade ausgedacht, Sie können mehr über solche Zahlen unter diesem Link erfahren mathworld.wolfram.com/LiouvillesConstant.html

Jurij S

@Arjang, aber das ist ein deterministischer Prozess, oder? Und übrigens, was meinst du mit „endlichem Automaten“? Jeder Prozess, den wir (als Menschheit) jemals durchgeführt haben, ist endlich

Jimjim

@YuriyS: Ein deterministischer Prozess ist nicht dasselbe wie eine deterministische Finite-State-Maschine, und ja, nicht nur das, was Sie gesagt haben, ist wahr, auch das gesamte Universum reicht nicht aus, um alle Ziffern der Quadratwurzel von zwei darzustellen. Vielleicht möchten Sie sich auch die Grenzen der Berechnung, die Omega-Zahl und die Ordnungen der Unendlichkeit ansehen.

Jurij S

@Arjang, das können wir beweisen

\sqrt{2}, e, π

$\sqrt{2}, e, \pi$ sind irrational, trotz der Tatsache, dass jede Dezimalerweiterung, die wir jemals erstellt haben, eine rationale Annäherung ist. Die Zahlen, nach denen ich frage, sollten als Grenze ins Unendliche genommen werden, vorausgesetzt, wir generieren weiterhin die CA

Jimjim

@YuriyS: Es tut mir leid, vielleicht fehlt mir hier etwas. Jede Zahl mit zufälligen Ziffern ist mit Sicherheit irrational. Ich werde die Frage noch einmal lesen, um die Frage zu verstehen.

Jimjim

Ich bin mir nicht sicher, was Sie fragen, aber philosophisch gesehen existieren in unserem Universum keine natürlichen Zahlen, sondern ihre Darstellungen.

Jurij S

@Arjang, jetzt, wo ich darüber nachdenke - meine Frage lautet eher: "Was betrachten wir als zufällig"? Sehen Sie sich das von mir verlinkte Papier an, vielleicht verstehen Sie, was ich frage

Zach466920

@ N74 "Sicher gibt es Irrationale und wir haben viele Beweise dafür in unserer kontinuierlichen Welt. Das Problem besteht darin, sie in einer Maschine zu erzeugen ... ohne unendlichen Speicher müssen Sie die Sequenz zuerst oder zuletzt wiederholen." Ich möchte Sie daran erinnern, dass dies Mathematik ist. Was Sie gesagt haben, betrifft die Machbarkeit in der Realität. Wir wissen jedoch beide, wie zuverlässig ein Indikator für die Machbarkeit die Möglichkeit vorhersagt.

Zach466920

Ich brauche eine Klärung, wie Sie Ihnen die bekommen

a_{n}

$a_n$ . Zum Beispiel für

a_{0}

$a_0$ Sie scheinen von oben in der Mitte zu beginnen und dann eine Binärzahl zu erstellen, indem Sie die Zellenautomaten für die Werte verwenden. Jeder Wert in der Mitte ist entweder

0

$0$ oder

1

$1$ . Zum Beispiel hat die erste Zeile

1

$1$ , dann hat der zweite

1

$1$ der dritte hat

0

$0$ usw?

Jurij S

@Zach466920, jede Zahl wird erstellt, indem Zellenwerte in einer vertikalen Spalte als 0 oder 1 genommen werden.

a_{0}

$a_0$ ist eine zentrale Säule. Du scheinst es richtig zu verstehen. Wenn ich Zeilen nehmen würde, hätte jede Zahl eine endliche Erweiterung, dh wäre rational

Antworten (2)

Irrationale Zahlen, die von einem deterministischen zellulären Automaten generiert werden?

Wenn Sie keine unendlichen Ziffern haben, ist Ihre Zahl rational. Und man kann nur unendlich viele Ziffern in unendlicher Zeit haben.
@ N74 Ja, aber zellulare Automaten wie dieser bleiben für immer bestehen. Das OP hat gerade die ersten paar Schritte gezeigt. Mit jedem neuen Schritt erhalten Sie mehr Ziffern.
@ N74, sagst du, dass es keine irrationalen Zahlen gibt? Niemand war in der Lage, unendliche Ziffern von zu erhalten $\pi$ noch
@YuriyS Ich sage, dass kein deterministischer Prozess eine irrationale Zahl erzeugen kann, es sei denn, er läuft für immer. Denken Sie an das klassische Beispiel der Konstruktion einer irrationalen Zahl: $a_0=0.1$ , $a_1=0.101$ , $a_2=0.101001$ , $a_3=0.1010010001$ ; $a_{\infty}$ ist doch alles transzendent $a_n$ rational sind.
@barrycarter Irrationale Zahlen sollten eine zählbare Unendlichkeit von Ziffern haben, lassen Sie den Algorithmus laufen und am Ende des Universums haben Sie eine irrationale Zahl. Keine maschinendarstellbare Zahl ist irrational.
@ N74 sagst du das noch einmal $\pi$ , $e$ , $\sqrt{2}$ , etc, gibt es nicht? Warum kann eine Cauchy-Folge nicht von einem zellularen Automaten (oder einer anderen Maschine) definiert werden?
@YuriyS wegen Zeit und Ressourcen: Keine Maschine hat keine Beschränkung für beide.
@ N74, tut mir leid, könnten Sie bitte Ihre Position zu irrationalen Zahlen im Allgemeinen erläutern? Existieren sie, obwohl wir sie nicht in endlicher Zeit berechnen können?
@YuriyS Sicherlich gibt es Irrationale und wir haben viele Beweise dafür in unserer kontinuierlichen Welt. Das Problem besteht darin, sie in einer Maschine zu generieren ... ohne unendlichen Speicher müssen Sie die Sequenz wiederholen, zuerst oder zuletzt.
Können wir zur Lösung dieses Problems sagen, dass wir eine Folge berechenbarer rationaler Zahlen haben, deren Grenzwert gegen eine irrationale Zahl konvergiert?
Der Punkt ist folgender: Kein deterministischer endlicher Automat kann irrationale Zahlen erzeugen.
@Arjang, dann gibt es überhaupt keine Möglichkeit, irrationale Zahlen zu generieren?
@YuriyS: Sicher, nehmen Sie zum Beispiel Binärziffern mit 0,10110011100011110000 ... das ist eine irrationale Zahl, vielleicht sogar transzendental. die Ziffern sind einfach zu generieren, solange sie sich nicht ab einigen Stellen wiederholen.
@YuriyS: Ich habe mir diese Zahl gerade ausgedacht, Sie können mehr über solche Zahlen unter diesem Link erfahren mathworld.wolfram.com/LiouvillesConstant.html
@Arjang, aber das ist ein deterministischer Prozess, oder? Und übrigens, was meinst du mit „endlichem Automaten“? Jeder Prozess, den wir (als Menschheit) jemals durchgeführt haben, ist endlich
@YuriyS: Ein deterministischer Prozess ist nicht dasselbe wie eine deterministische Finite-State-Maschine, und ja, nicht nur das, was Sie gesagt haben, ist wahr, auch das gesamte Universum reicht nicht aus, um alle Ziffern der Quadratwurzel von zwei darzustellen. Vielleicht möchten Sie sich auch die Grenzen der Berechnung, die Omega-Zahl und die Ordnungen der Unendlichkeit ansehen.
@Arjang, das können wir beweisen $\sqrt{2}, e, \pi$ sind irrational, trotz der Tatsache, dass jede Dezimalerweiterung, die wir jemals erstellt haben, eine rationale Annäherung ist. Die Zahlen, nach denen ich frage, sollten als Grenze ins Unendliche genommen werden, vorausgesetzt, wir generieren weiterhin die CA
@YuriyS: Es tut mir leid, vielleicht fehlt mir hier etwas. Jede Zahl mit zufälligen Ziffern ist mit Sicherheit irrational. Ich werde die Frage noch einmal lesen, um die Frage zu verstehen.
Ich bin mir nicht sicher, was Sie fragen, aber philosophisch gesehen existieren in unserem Universum keine natürlichen Zahlen, sondern ihre Darstellungen.
@Arjang, jetzt, wo ich darüber nachdenke - meine Frage lautet eher: "Was betrachten wir als zufällig"? Sehen Sie sich das von mir verlinkte Papier an, vielleicht verstehen Sie, was ich frage
@ N74 "Sicher gibt es Irrationale und wir haben viele Beweise dafür in unserer kontinuierlichen Welt. Das Problem besteht darin, sie in einer Maschine zu erzeugen ... ohne unendlichen Speicher müssen Sie die Sequenz zuerst oder zuletzt wiederholen." Ich möchte Sie daran erinnern, dass dies Mathematik ist. Was Sie gesagt haben, betrifft die Machbarkeit in der Realität. Wir wissen jedoch beide, wie zuverlässig ein Indikator für die Machbarkeit die Möglichkeit vorhersagt.
Ich brauche eine Klärung, wie Sie Ihnen die bekommen $a_n$ . Zum Beispiel für $a_0$ Sie scheinen von oben in der Mitte zu beginnen und dann eine Binärzahl zu erstellen, indem Sie die Zellenautomaten für die Werte verwenden. Jeder Wert in der Mitte ist entweder $0$ oder $1$ . Zum Beispiel hat die erste Zeile $1$ , dann hat der zweite $1$ der dritte hat $0$ usw?
@Zach466920, jede Zahl wird erstellt, indem Zellenwerte in einer vertikalen Spalte als 0 oder 1 genommen werden. $a_0$ ist eine zentrale Säule. Du scheinst es richtig zu verstehen. Wenn ich Zeilen nehmen würde, hätte jede Zahl eine endliche Erweiterung, dh wäre rational

Zach466920 · Answer 1

Die Antwort selbst ist nicht sehr überraschend oder aufschlussreich, also sorry :/

Erstens, da Sie ein Bild von Regel 30 gepostet haben, das hier besprochen wird , werden wir nur die Nummerngenerierung von dieser Zertifizierungsstelle in Betracht ziehen.

Erinnern Sie sich zweitens an die Definition einer irrationalen Zahl ,

Eine irrationale Zahl ist eine Zahl, die nicht als Bruch p/q für beliebige ganze Zahlen p und q ausgedrückt werden kann.

Folge 1:

Irrationale Zahlen haben Dezimalerweiterungen, die weder enden noch periodisch werden.

Beweis: Angenommen, die Dezimalentwicklung wiederholt sich. Dann ist die Zahl per Definition rational . Somit ist unsere Annahme falsch, und die Folgerung ist wahr.

Nun wurde von Jen 1990 bewiesen , dass mit dem Anfangszustand einer einzelnen schwarzen Zelle die Farbfolge, die in zwei benachbarten Zellen erreicht wird, nicht periodisch ist. Bestätigt durch Gray 2003 .

Wenn wir also eine Folge von Zahlen definieren, indem wir die von Regel 30 generierten Zellzustände verwenden, dann sind die Ziffern nicht periodisch. Nach Korollar 1, wenn die Ziffern nicht periodisch sind, dann ist die Zahl irrational.

Schauen wir uns also Ihre Frage(n) an

Können wir beweisen/widerlegen, dass diese Zahlen irrational sind?

Wir können beweisen, dass diese Zahlen irrational sind, für Regel 30.

Transzendental?

Fast sicher.

Was ist mit anderen solchen „zufälligen“ zellularen Automaten?

Jeder zellulare Automat mit nichtperiodischer Evolution wird ebenfalls irrationale Zahlen erzeugen.

Wenn Sie "fast sicher" sagen, nehme ich an, dass es sehr überraschend wäre, wenn irgendetwas algebraisch wäre.
@ user254665 Eigentlich meine ich es im mathematischen Sinne. Da auch Regel 30 chaotisch ist, entwickeln sich die Zellen pseudozufällig. Mit ziemlicher Sicherheit ist eine solche Zahl transzendental.
Kleiner Punkt: Für Regel 30 bleibt es, obwohl höchst unwahrscheinlich, eine offene Frage, ob nicht jede unendliche Spalte niemals in einen Zyklus verfällt oder nicht; es hat sich gezeigt, dass dies höchstens eine Spalte kann. Wenn es irgendwie eine sich wiederholende Spalte gäbe (es gibt absolut keine, aber niemand kann es beweisen), wäre diese Spalte rational.

Gro-Tsen · Answer 2

Während fast alle reellen Zahlen transzendent sind, ist es teuflisch schwierig, dies für bestimmte reelle Zahlen zu beweisen, insbesondere für solche, die durch ihre Basis gegeben sind $b$ Erweiterung. (Für die „natürlichen“ Größen, für die ein Beweis der Transzendenz bekannt ist, geschieht dies im Allgemeinen dadurch, dass diese Größen als bestimmte Werte spezieller Funktionen betrachtet und Techniken aus der Analyse solcher Funktionen verwendet werden.) Im Gegensatz zur Irrationalität (eine Zahl ist irrational, wenn ihre Basis $b$ Expansion ist schließlich nicht periodisch), es gibt nichts Analoges zur Transzendenz.

Selbst für die sehr einfach aussehende Champernowne-Konstante ( $0.12345678910111213...$ ), war es schwierig, seine Transzendenz zu beweisen . Sie sollten keinen Beweis der Transzendenz von Größen erwarten, deren Basis $b$ Erweiterungen werden durch zellulare Automaten definiert.

Es gibt jedoch ein bemerkenswertes Ergebnis, das zumindest eine gewisse Ähnlichkeit mit dem aufweist, wonach Sie fragen, zumindest in dem Sinne, dass die Schlüsselwörter "automaton", "base $b$ Expansion" und "Transzendenz" erscheinen darin:

Wenn $x$ ist eine reelle Zahl (und $b\geq 2$ eine ganze Zahl), so dass die Basis $b$ Erweiterung von $x$ ist nicht schließlich periodisch, und " $b$ -automatisch" in dem Sinne, dass die $i$ -te Dezimalstelle von $x$ in der Basis $b$ kann von einem endlichen Automaten aus der Basis berechnet werden $b$ Erweiterung von $i$ sich dann $x$ ist transzendental.

Ein erster „Beweis“ erschien als: Loxton & van der Poorten, „ Arithmetic properties of automata: regular sequences “, J. Reine Angew. Mathematik. 392 (1988), 57–69; Dieses Papier enthält jedoch einen Fehler. Ein richtiger Beweis, zusammen mit den dazugehörigen Ergebnissen und Vermutungen, ist erst viel später erschienen: Adamczewski & Bugeaud, „ On the complexity of algebraic numbers I. Expansions in integer bases “, Ann. von Math. 165 (2007), 547–565. ( Hier ist eine Umfrage zu solchen Fragen, obwohl sie sich anscheinend nicht bewusst ist, dass das Papier von Loxton & van der Poorten fehlerhaft ist.)

Dieses Ergebnis impliziert zum Beispiel, dass die Zahl, deren binäre Erweiterung die Morse-Thue-Folge ist , nämlich, $0.01101001100101101001...$ , ist transzendent (weil es sicherlich automatisch und nicht periodisch ist). Dies kommt sicherlich der Menge, nach der Sie gefragt haben, am nächsten.

(Bemerkenswerterweise gibt es für formale Potenzreihen über endlichen Körpern ein Ergebnis von Christol, Kamae, Mendès-France und Rauzy, das im Wesentlichen das „Gegenteil“ des oben zitierten aussagt: Die Koeffizienten der formalen Potenzreihen sind automatisch iff die Potenzreihe ist algebraisch .)

Ich bin mir nicht sicher, warum Sie so pessimistisch sind, zu beweisen, dass eine von zellularen Automaten generierte Zahl transzendent ist, wenn Sie dann sofort ein sehr ähnliches (und wunderbares) Ergebnis darüber anführen, wie endliche, von Automaten generierte Zahlen transzendent sind .
@JackM Weil die Theorie der endlichen Automaten äußerst eingeschränkt und gut verstanden ist und es sich selbst dann als immens schwierig herausstellte, die Transzendenz der von ihnen erkannten Erweiterungen zu beweisen; Zellulare Automaten können so ziemlich alles, ich denke, es ist unvernünftig, dort auf Transzendenzergebnisse zu hoffen (aber ich würde mich natürlich freuen, wenn ich mich irre!).
@Gro-Tsen, vielen Dank für deine Antwort. Es tut mir leid, ich konnte Sie nicht belohnen, aber die andere Antwort erscheint mir relevanter
@Gro-Tsen Ich denke, es gibt hier zwei verschiedene Fragen: "Können wir angesichts einer CA beweisen, dass eine der von ihr generierten Zahlen transzendent ist?" und 'Können wir eine CA ausstellen, die auf diese Weise transzendente Zahlen erzeugt?' Die Antwort auf die erste ist wahrscheinlich so schwierig, wie Sie sagen, aber ich denke, die Antwort auf die zweite sollte positiv sein, indem Sie eine angemessene Konstruktion übersetzen.

Irrationale Zahlen, die von einem deterministischen zellulären Automaten generiert werden?

Jurij S

N74

Benutzer2469

Jurij S

N74

N74

Jurij S

N74

Jurij S

N74

Benutzer2469

Jimjim

Jurij S

Jimjim

Jimjim

Jurij S

Jimjim

Jurij S

Jimjim

Jimjim

Jurij S

Zach466920

Zach466920

Jurij S

Antworten (2)

Zach466920

Daniel Wainfleet

Zach466920

Trevor

Gro-Tsen

Jack M

Gro-Tsen

Jurij S

Steven Stadnicki