Unterstützt eine laute Version von Conways Lebensspiel universelle Berechnungen?

30

Wikipedia zitiert : "[Conways Spiel des Lebens] hat die Kraft einer universellen Turing-Maschine: Das heißt, alles, was algorithmisch berechnet werden kann, kann innerhalb von Conways Spiel des Lebens berechnet werden."

Umfassen solche Ergebnisse auch laute Versionen von Conways Game of Life? Die einfachste Variante ist, dass nach jeder Runde jede lebende Zelle mit einer geringen Wahrscheinlichkeit stirbt und jede tote Zelle mit einer geringen Wahrscheinlichkeit (unabhängig) lebendig wird .ts

Eine andere Möglichkeit besteht darin, die folgende probabilistische Variante der Spielregel selbst zu betrachten.

  • Jede lebende Zelle mit weniger als zwei lebenden Nachbarn stirbt mit einer Wahrscheinlichkeit von .1t
  • Jede lebende Zelle mit zwei oder drei lebenden Nachbarn lebt mit einer Wahrscheinlichkeit von bis zur nächsten Generation.1t
  • Jede lebende Zelle mit mehr als drei lebenden Nachbarn stirbt mit einer Wahrscheinlichkeit von 1t .
  • Jede tote Zelle mit genau drei lebenden Nachbarn wird mit einer Wahrscheinlichkeit von 1-t zu einer lebenden Zelle 1t.

Frage: Unterstützen diese lauten Versionen des Spiels des Lebens noch universelle Berechnungen? Wenn nicht, was kann über ihre "Rechenleistung" gesagt werden?

Verwandte Informationen zur Rechenleistung von Zellularautomaten und verrauschten Versionen von Zellularautomaten werden ebenfalls sehr geschätzt.

(Diese Frage entstand aus dieser Frage zu MathOverflow. Vincent Beffaras Antwort zu MO lieferte interessante Referenzen für verwandte Ergebnisse zu rechnerischen Aspekten von verrauschten zellularen Automaten.)

Gil Kalai
quelle
2
@vzn 1) nein, das ist nicht die "wahre Frage", es ist eine ganz andere Frage; Gils Frage betrifft die Robustheit eines einfachen Rechenmodells gegenüber Rauschen, nicht die Macht der Zufälligkeit; 2) TMs mit einem zufälligen Band sind nicht leistungsfähiger als deterministische TMs, siehe diese Antwort: cstheory.stackexchange.com/a/1415/4896
Sasho Nikolov
2
Die eigentliche Frage ist hier, ob die stochastischen / lauten Versionen des "Game of Life" noch Berechnungen unterstützen. (Wenn diese Versionen Berechnungen in P unterstützen, reicht ihre Leistung möglicherweise bis zu BPP.) Es ist möglich, dass die Rechenleistung dieser stochastischen Versionen des Spiels des Lebens viel geringer ist.
Gil Kalai
3
Vielleicht sage ich das Offensichtliche, aber Sie können eine Konfiguration einfach genügend oft duplizieren, um mit hoher Wahrscheinlichkeit zu gewährleisten, dass in einer Version der Konfiguration nicht einmal eine Zelle gespiegelt ist. Mein persönlicher Glaube ist, dass wir viel, viel besser können, aber es ist zumindest eine einfache Untergrenze.
User834
4
Ich bin mir nicht sicher, ob die Frage klar definiert ist. Angenommen, . Es scheint mir, dass Sie in der Lage sein könnten, einen Computer zu finden, der alle Ein-Bit-Fehler im "Game of Life" behandelt und Ihnen eine fehlertolerante Berechnung ermöglicht, es sei denn, Sie erhalten spontan einen großen Fehlerblock auf einmal. Aber ich glaube nicht, dass irgendetwas allen Fehlern widerstehen kann. Angenommen, die Fehler erzeugen spontan einen böswilligen Gegner, der die Berechnung unterbrechen soll. Möglicherweise können Sie nachweisen, dass Ihre Berechnung mit einer Wahrscheinlichkeit von aber mit einer Wahrscheinlichkeit von fehlschlägt . Zählt das? > 1 - 10 - 9 > 10 - 10000t=10-9>1-10-9>10-10000
Peter Shor
2
Peter, wenn deine Berechnung mit Wahrscheinlichkeit 2/3 erfolgreich ist, bin ich glücklich.
Gil Kalai

Antworten:

8

Hier sind einige "in der Nähe beste" Referenzen, für was es sich lohnt. Es scheint, als würde man diese Frage auf eine Frage zu "lauten Turing-Maschinen" reduzieren, die (vor kurzem) untersucht wurden und anscheinend den nächstgelegenen relevanten Bereich in der Literatur darstellen. Die grundlegende / allgemeine / vernünftige Antwort scheint zu sein, dass, wenn der TM Rauschen widerstehen / korrigieren kann (wie in diesen Referenzen gezeigt wird), es sehr wahrscheinlich ist, dass der CA dies auch innerhalb einiger Grenzen / Schwellenwerte kann.

Die Frage, wie eine "verrauschte CA" zu einer "verrauschten TM" (und umgekehrt) reduziert werden kann, ist offener. Es mag nicht schwer sein, aber es scheint keine veröffentlichte Forschung auf dem Gebiet zu geben. Ein weiteres Problem ist, dass es sich bei dem verrauschten TM um ein neues Modell handelt und es daher möglicherweise mehrere (natürliche?) Möglichkeiten gibt, ein verrauschtes TM darzustellen. In den folgenden Abhandlungen werden beispielsweise Störungen in der Zustandsübergangsfunktion behandelt. Ein weiteres natürliches Modell sind Störungen in den Bandsymbolen (letztere sind eher mit verrauschten Zertifizierungsstellen verbunden?). Möglicherweise besteht eine Beziehung zwischen beiden.

  • Fehlertolerante Turingmaschine von Ilir Capuni, 2012 (Doktorarbeit)

    Die Turing-Maschine ist das am besten untersuchte universelle Rechenmodell. Diese Arbeit untersucht die Frage, ob es eine Turing-Maschine gibt, die zuverlässig rechnen kann, auch wenn Verstöße gegen ihre Übergangsfunktion mit einer geringen Wahrscheinlichkeit unabhängig voneinander auftreten.

    In dieser Arbeit beweisen wir die Existenz einer Turing-Maschine, die mit einem Polynom über Kopf jede andere Turing-Maschine simulieren kann, auch wenn sie Störungen des oben genannten Typs ausgesetzt ist, und beantworten damit die seit 25 Jahren offene Frage.

  • Eine Turing-Maschine, die isolierten Ausbrüchen von Fehlern widersteht von Ilir Capuni und Peter Gacs, 2012
  • Laut Turing Machines von Eugene Asarin und Pieter Collins, 2005
(Eine andere Frage: Könnte es einen Zusammenhang zwischen lauten TMs und probabilistischen Turing-Maschinen geben ?)

vzn
quelle
7

Gil fragt, ob der GL zeitlich unabhängig von der Größe alles über seine ursprüngliche Konfiguration vergisst, wenn jede Zelle die Übergangsfunktion unabhängig von anderen Zellen mit einer geringen Wahrscheinlichkeit "missachtet".

Dies ist meines Wissens für den GL nicht bekannt. Es ist jedoch eine sehr interessante Frage. Wenn es dem Lärm standhält, sollte es seine Universalität bewahren.

Ein kurzer Überblick über den Stand der Technik lautet wie folgt.

  1. Die Toom-Regel kann mit einer geringen Wahrscheinlichkeit ein Bit für immer Fehler speichern, die unabhängig voneinander auftreten.
  2. Es wurde allgemein angenommen (die Vermutung positiver Raten), dass alle 1-dim CA ergodisch sind, bis P. Gacs seine mehrskalige CA konstruierte, die jede andere CA mit moderatem Overhead simulieren kann, selbst wenn sie dem oben genannten Rauschen ausgesetzt ist.
  3. Die Frage, ob die Regel G (acs) K (urdiumov) L (evin) in Gegenwart des obigen Rauschens ein Bit für immer speichern kann, ist noch offen. Kihong Park - ein Schüler von Gacs - zeigte, dass dies nicht der Fall ist, wenn der Lärm voreingenommen ist.
  4. Als die Arbeit in 2 veröffentlicht wurde, fragte M. Blum , ob ein TM seine Berechnung fortsetzen könne, wenn bei jedem Schritt der Übergang nicht mit einer geringen Wahrscheinlichkeit unabhängig von anderen Schritten gemäß der Übergangsfunktion ausgeführt wird, vorausgesetzt, dass die Informationen in gespeichert sind Das Band weit vom Kopf zerfällt nicht. Eine positive Antwort gab im Jahr 2012 I. Capuni (ein weiterer Schüler von Gacs).
user8719
quelle
"Wenn es nicht ergodisch ist, dann wird es seine Universalität bewahren" ... haben Sie irgendwelche Beweise für diese Aussage? Ist das ein Satz? Wo ist es bewiesen? Ich glaube, dass Gacs Arbeit zeigt, dass dies in mindestens einem Fall zutrifft, aber ich sehe nicht, wie das beweist, dass es für Conways Spiel des Lebens gilt.
Peter Shor
Vielen Dank für den Hinweis. Es ist kein Satz, sondern eine interessante offene Frage. Nicht ergodisch zu sein, scheint zu wenig, um nach einer so starken Aussage zu fragen.
User8719
3

Denken Sie für den Anfang daran, dass die Forschung in Conways Game of Life noch nicht abgeschlossen ist und zukünftige Entwicklungen möglicherweise eine weitaus weniger komplizierte Lösung darstellen.

Nun dann. Interessanterweise ist dies ein Thema, das der Biologie und der Quantenphysik in etwa so nahe kommt wie der traditionellen Informatik. Die eigentliche Frage ist, ob ein Gerät einer zufälligen Änderung seines Zustands effektiv widerstehen kann. Die einfache Antwort ist, dass es unmöglich ist, eine solche Maschine perfekt zu machenresistent gegen solche zufälligen Veränderungen. Dies gilt natürlich in etwa der gleichen Weise, wie die Quantenmechanik scheinbar unmögliche Ereignisse verursachen könnte. Was verhindert, dass diese Ereignisse auftreten (was die meisten Menschen dazu veranlasst, sie für absolut unmöglich zu erklären), ist die erstaunlich geringe Wahrscheinlichkeit, dass ein solches Ereignis eintritt. Eine Wahrscheinlichkeit, die durch den großen Unterschied zwischen dem Quantenniveau und dem menschlichen Niveau so klein gemacht wird. Auf ähnliche Weise ist es möglich, eine Zustandsmaschine herzustellen, die gegen kleine Grade zufälliger Änderungen resistent ist, indem sie einfach so groß und redundant gemacht wird, dass jede festgestellte "Änderung" praktisch Null ist, aber die Annahme ist, dass dies nicht das Ziel ist. Vorausgesetzt, dies kann auf die gleiche Weise erreicht werden, wie Tiere und Pflanzen beständig gegen Strahlung oder physische Schäden sind.

Die Frage ist dann vielleicht nicht, wie man verhindert, dass schwache Störungen zu viel Schaden anrichten, sondern wie man sich von so viel Schaden wie möglich erholt. Hier wird die Biologie relevant. Tiere und Pflanzen haben tatsächlich genau diese Fähigkeit auf zellulärer Ebene. (Bitte beachten Sie: Ich spreche in dieser Antwort von Zellen im biologischen Sinne.) Nun, in Conways Lebensspiel, der Gedanke, ein Computergerät im Maßstab einzelner Zellen zu bauen ist ansprechend (es macht solche Kreationen immerhin viel kleiner und effizienter), aber während wir selbstreproduzierende Computer bauen können ( siehe Zwillinge ), ignoriert dies die Tatsache, dass das Konstruktorobjekt selbst durch Störungen beschädigt werden kann.

Eine andere, widerstandsfähigere Möglichkeit, dies zu lösen, besteht darin, Computer aus sich selbst reproduzierenden redundanten Teilen (beispielsweise biologischen Zellen) zu bauen, die ihre Operationen ausführen, sich reproduzieren und ersetzt werden.

An dieser Stelle können wir eine weitere interessante reale Parallele erkennen. Diese geringen Störungen ähneln den Auswirkungen von Strahlung. Dies ist besonders bemerkenswert, wenn Sie die Art des Schadens betrachten, der an Ihren zellularen Automaten angerichtet werden kann. Es ist einfach, in Conways Spiel des Lebens den Kaskadenausfall oder den "Tod" einer Zelle auszulösen, ähnlich wie dies bei vielen Zellen der Fall ist, die Strahlung ausgesetzt sind. Im schlimmsten Fall besteht jedoch die Möglichkeit einer Mutation, bei der eine "krebsartige" Zelle erzeugt wird, die weiterhin fehlerhafte Kopien von sich selbst reproduziert, die den Rechenprozess nicht unterstützen oder falsche Ergebnisse liefern.

Wie ich bereits sagte, ist es unmöglich, ein System zu erstellen, das absolut narrensicher ist. Es ist jedoch immer unwahrscheinlicher, dass ein Fehler das gesamte System beeinträchtigt. Natürlich ist die grundlegende Frage hier wirklich "sind probabilistische Simulationen selbst vollständig", was bereits als wahr befunden wurde . Ich hätte diese grundlegende Frage anfangs beantwortet, außer dass es nicht das war, was Sie gefragt haben.

Hawkwing
quelle
Wow! Vielen Dank für die Drive-by-Downvote! Jedenfalls habe ich meinen Beitrag überarbeitet und einige Informationen und Quellen hinzugefügt. Tut mir leid, dass ich nicht die Zeit hatte, das zu tun, als ich dies zum ersten Mal gepostet habe. Ich könnte diese Antwort noch weiter modifizieren, um sie an die Standards der Community anzupassen, wenn nicht der Grund für die Ablehnung angegeben worden wäre.
Hawkwing
5
Als Nichtwähler sehe ich nicht, wie dies Gils Frage beantwortet. Sie gehen der Frage nach , ob „jede Vorrichtung kann wirksam wider zufällige Veränderungen in ihren Zustand“, das ist nicht , was Gil gefragt.
András Salamon
Vielen Dank (diesmal nicht sarkastisch) für den Kommentar, András Salamon. Ich würde es für nützlich halten, aber ich bin immer noch ein neuer Benutzer auf dieser Überlaufseite. Wie auch immer, es tut mir leid, dass meine Antwort nicht zum Thema gehört. Ich habe die Frage vielleicht lockerer angesprochen, als ich beabsichtigt hatte, aber ich glaube, meine Antwort beantwortet die ursprüngliche Frage, indem ich eine ähnliche Frage beantworte und dann Parallelen zwischen den beiden ziehe. Ist das vielleicht ein zu umständlicher Weg zu antworten?
Hawkwing
0

Ich erinnere mich an xkcd 505: A Bunch of Rocks .

Jeder Computer in der realen Welt ist einem gewissen Geräuschpegel ausgesetzt. Bei einer Simulation eines Universalcomputers im idealen, unendlichen Conway-Universum wird die mittlere Zeit zwischen Ausfällen von den technischen Details seiner Konstruktion abhängen. Es wird zuverlässig für einen wahrscheinlich quantifizierbaren Zeitraum berechnet, unzuverlässig für einen Zeitraum akkumulierender Fehler und dann überhaupt nicht .

Ich würde erwarten, dass ein Fuzzy-Logik- oder Quantenüberlagerungsmodell klar zeigt, welche Zuverlässigkeit von einer bestimmten Konstruktion zu erwarten ist. Möglicherweise möchten Sie die erwarteten Ausgaben verschiedener Komponenten simulieren, anstatt alle Zellen zu durchlaufen, unabhängig davon, inwieweit sie voneinander isoliert werden können. Man könnte in der Lage sein, erwartete Störungen durch fehlerhafte Komponenten zu quantifizieren. Ein genetischer Algorithmus sollte der beste Weg sein, um fehlerbehaftete, widerstandsfähige, korrigierende Komponenten mit MTBFs zu entwickeln, die für eine gegebene Rauschverteilung so groß sind, wie es gewünscht wird.

user130144
quelle
(geheimnisvolle Abstimmung hier) Eine quantitative Antwort wäre sehr spekulativ. Eine genauere Antwort als "Ja, bedingt" kann es nicht geben, ohne ausgiebig an einer ausgewählten Implementierung einer UTM zu experimentieren. Ein normaler Computer in einer Umgebung mit hoher Strahlung ist praktisch immer noch eine UTM, wenn auch nur für kurze Zeit.
user130144