Reversible Turing-Tarpits?

Bei dieser Frage geht es darum, ob es bekannte reversible Turing-Tarpits gibt, wobei "reversibel" im Sinne von Axelsen und Glück bedeutet und "Tarpit" ein viel informelleres Konzept ist (und möglicherweise keine sehr gute Wortwahl ist). aber ich werde mein Bestes geben, um zu erklären, was ich damit meine.

Was ich mit "Tarpit" meine

Einige Berechnungsmodelle sind so konzipiert, dass sie in irgendeiner Weise nützlich sind. Andere sind einfach vollständig und haben keine besonders nützlichen Eigenschaften. Diese sind als "Turing-Tarpits" bekannt. Beispiele sind die Sprache Brainfuck , der zellulare Automat nach Regel 110 und die Sprache Bitwise Cyclic Tag (die mir gefällt, weil sie sehr einfach zu implementieren ist und jede Binärzeichenfolge ein gültiges Programm ist).

Es gibt keine formale Definition von "Turing-Tarpit", aber für diese Frage meine ich ein ziemlich einfaches System (in Bezug auf eine kleine Anzahl von "Regeln"), das "zufällig" vollständig ist, ohne sein innerer Zustand hat eine offensichtliche semantische Bedeutung. Der wichtigste Aspekt für meine Zwecke ist eher die Einfachheit der Regeln als das Fehlen einer offensichtlichen Semantik. Grundsätzlich sprechen wir über die Dinge, über die Stephen Wolfram einmal ein sehr großes Buch geschrieben hat , obwohl er das Wort "Tarpit" nicht verwendet hat.

Was ich mit "reversibel" meine

Ich interessiere mich für reversible Berechnungen. Insbesondere interessiere ich mich für Sprachen, die im Sinne von Axelsen und Glück vollständig sind , was bedeutet, dass sie jede berechenbare Injektionsfunktion berechnen können und nur Injektionsfunktionen berechnen können. Nun gibt es viele Rechenmodelle, die in diesem Sinne reversibel sind, wie Axelsens reversible Universal-Turing-Maschine oder die hochreversible Sprache Janus . (Es gibt viele andere Beispiele in der Literatur; es ist ein aktives Forschungsgebiet.)

Es ist anzumerken, dass Axelsen und Glücks Definition der Vollständigkeit von r-Turing ein anderer Ansatz für reversibles Rechnen ist als der übliche Ansatz von Bennett. Bei Bennetts Ansatz darf ein System "Mülldaten" erzeugen, die am Ende der Berechnung weggeworfen werden. Unter solchen Bedingungen kann ein reversibles System vollständig sein. Nach dem Ansatz von Axelsen und Glück darf das System jedoch keine solchen "Junk-Daten" erzeugen, was die Klasse der Probleme einschränkt, die es berechnen kann. (Daher "r-Turing komplett" statt "Turing komplett".)

_{Hinweis: Das Axelsen- und Glück-Papier befindet sich hinter einer Paywall. Dies ist bedauerlich - meines Wissens gibt es derzeit keine nicht kostenpflichtige Ressource zum Thema Vollständigkeit von r-Turing. Ich werde versuchen, eine Wikipedia-Seite zu starten, wenn ich Zeit habe, aber keine Versprechen.}

Wonach ich suche

Die oben erwähnten Beispiele für reversibles Rechnen sind alle eher "semantisch beladen". Dies ist in den meisten Kontexten eine gute Sache, bedeutet jedoch, dass die Regeln, die erforderlich sind, um ihren Status bei jedem Zeitschritt zu aktualisieren, ziemlich komplex sind. Ich suche die "Tarpits" des reversiblen Rechnens. Das heißt, mehr oder weniger willkürliche Systeme mit recht einfachen Regeln, die "zufällig" vollständige Sprachen r-Turing sind. Ich wiederhole, dass es keine formale Definition für das gibt, wonach ich suche, aber ich werde es wissen, wenn ich es sehe, und ich denke, es ist eine vernünftige Sache, danach zu fragen.

Es gibt eine Reihe von Dingen, von denen ich weiß, dass sie fast zur Rechnung passen, aber nicht ganz. Es gibt mehrere reversible zellulare Automaten, von denen gezeigt wurde, dass sie vollständig sind. Langtons Ameise (eine Art zweidimensionale Turing-Maschine mit einer ziemlich willkürlichen und recht einfachen reversiblen Zustandsübergangsfunktion) ist ebenfalls Turing vollständig, solange ihre Anfangsbedingungen unendlich viele sich wiederholende Muster enthalten dürfen. Bei diesen Systemen ist es jedoch nicht trivial, eine Zuordnung von ihrem Status zu einer "Ausgabe" so zu definieren, dass keine Junk-Daten weggeworfen werden. Ich interessiere mich speziell für Systeme, bei denen man sich vorstellen kann, dass sie eine Eingabe annehmen, eine Folge von (reversiblen) Transformationen darauf ausführen und dann (falls sie enden) eine Ausgabe zurückgeben.

(Ich hoffe, dass diese Frage leichter zu beantworten ist als meine vorherige verwandte Frage zu einem reversiblen Äquivalent zum Lambda-Kalkül.)

"r-complete" scheint ein relativ neues Konzept zu sein, das von Axelsen und Glück ~ 2011 erfunden wurde und von anderen Autoren möglicherweise nicht sehr berücksichtigt wird. Sie fragen sich, ob es einen Beweis gibt, der sich von Turing complete unterscheidet.

Ich nehme diese ausführliche und umständliche Frage, um sie im Grunde zu stellen:

• ein einfaches Turing-Komplettsystem
• reversibel

Versuchen Sie es mit Turing-vollständigen reversiblen zellularen Automaten, z.

• Reversible universelle zelluläre Automaten mit zwei Zuständen in drei Dimensionen Miller / Fredkin

  Eine neuartige reversible Zellularautomatik (RCA) mit zwei Zuständen wird beschrieben. Es wird gezeigt, dass dieser dreidimensionale RCA universell berechnet werden kann. Zusätzlich wird der Nachweis erbracht, dass dieser Cinch universell einsetzbar ist.

• K. Imai und K. Morita, Ein rechnerisch-universeller zweidimensionaler dreieckiger reversibler Zellautomat mit 8 Zuständen, Theoretical Computer Science 231 (2000), No. 2, 181–191.

  Zusammenfassung: Ein reversibler zellularer Automat (RCA) ist ein zellularer Automat (CA), dessen globale Funktion injektiv ist und für den jede Konfiguration höchstens einen Vorgänger hat. Margolus zeigte, dass es eine rechnerunabhängige zweidimensionale 2-Zustands-RCA gibt. Da seine RCA jedoch einen uneinheitlichen Nachbarn hat, schlugen Morita und Ueno eine 16-Zustands-RCA mit rechnerunabhängiger Berechnung unter Verwendung partitionierter zellularer Automaten (PCA) vor. Da PCA als Unterklasse der Standard-CA betrachtet werden kann, haben ihre Modelle einen Standardnachbarn. In diesem Artikel zeigen wir, dass die Anzahl der Zustände der Modelle von Morita und Ueno reduziert werden kann. Um die Anzahl der Zustände aus ihren Modellen mit isotropen und bitschonenden Eigenschaften zu verringern, haben wir einen dreieckigen 3-Nachbarn verwendet, und daher kann ein RCA mit 8 Zuständen möglich sein. Dies ist der kleinste zweidimensionale RCA-Zustand unter der Bedingung isotroper Eigenschaften im Rahmen von PCA. Wir zeigen, dass unser Modell grundlegende Schaltungselemente wie Einheitsdrähte, Verzögerungselemente, Kreuzungsdrähte, Schaltgatter und inverse Schaltgatter simulieren kann, und es ist möglich, ein Fredkin-Gatter durch Kombinieren dieser Elemente zu konstruieren. Da das Fredkin-Gatter als universelles Logikgatter bekannt ist, verfügt unser Modell über Rechenuniversalität.

Es wurde als Referenz in dieser Umfrage unter Zertifizierungsstellen gefunden, die andere hilfreiche Hinweise auf die Untersuchung haben könnten (z. B. siehe Abschnitt 7, Reversibilität und Universalität). (Bei 17 Seiten und 86 Refs ist der Titel fast ironisch.)

Allgemeinheiten IN Zellularautomaten A (SHORT) SURVEY Ollinger