Ein Anhängsel-System ist ein deterministisches rechenbetontes Modell, das von Emil Leon Post 1943 als eine einfache Form von Post kanonisches System veröffentlicht ist. Ein Anhängsel-System kann auch als eine abstrakte Maschine angesehen werden, genannt eine Anhängsel-Maschine von Post (um mit Post-Turing Maschinen nicht verwirrt zu sein) — kurz ist eine Zustandsmaschine, deren nur binden, eine FIFO Warteschlange der unbegrenzten Länge, solch, dass in jedem Übergang die Maschine das Symbol an der Spitze der Warteschlange liest, löscht eine festgelegte Zahl von Symbolen vom Kopf, und zum Schwanz hängt eine dem gelöschten Symbol vorzugeteilte Symbol-Schnur an. (Weil alle angezeigten Operationen in jedem Übergang durchgeführt werden, hat eine Anhängsel-Maschine ausschließlich nur einen Staat.)

Definition

Ein Anhängsel-System ist ein Drilling (M, A, P), wo

• M ist eine positive ganze Zahl, genannt die Auswischen-Zahl.
• A ist ein begrenztes Alphabet von Symbolen, von denen eines ein spezielles stockendes Symbol ist. Alle begrenzt (vielleicht leer) Schnuren auf A werden Wörter genannt.
• P ist eine Reihe von Produktionsregeln, ein Wort P (x) zuteilend (hat eine Produktion genannt) zu jedem Symbol x in A. Wie man sieht, spielt die Produktion (sagen P ), zugeteilt dem stockenden Symbol unten keine Rolle in der Berechnung, aber für die Bequemlichkeit wird genommen, um P = zu sein.

Der Begriff M Anhängsel-System wird häufig gebraucht, um die Auswischen-Zahl zu betonen. Definitionen ändern sich etwas in der Literatur (vgl Verweisungen), diejenige präsentiert, hier dieser von Rogozhin seiend.

• Ein stockendes Wort ist ein Wort, das entweder mit dem stockenden Symbol beginnt, oder dessen Länge weniger ist als M.
• Eine Transformation t (hat die Anhängsel-Operation genannt), wird auf dem Satz von nichtstockenden Wörtern definiert, dass solch, wenn x das leftmost Symbol eines Wortes S anzeigt, dann ist t (S) das Ergebnis, die leftmost M Symbole von S zu löschen und das Wort P (x) rechts anzuhängen.
• Eine Berechnung durch ein Anhängsel-System ist eine begrenzte Folge von erzeugten Wörtern durch das Wiederholen der Transformation t, das Starten mit einem am Anfang gegebenen Wort und den Halt, wenn ein stockendes Wort erzeugt wird. (Durch diese Definition, wie man betrachtet, besteht eine Berechnung nicht, wenn ein stockendes Wort in begrenzt noch viel Wiederholungen nicht erzeugt wird. Alternative Definitionen erlauben nichtstockende Berechnung, zum Beispiel durch das Verwenden einer speziellen Teilmenge des Alphabetes, um Wörter zu identifizieren, die Produktion verschlüsseln.)

Der Gebrauch eines stockenden Symbols in der obengenannten Definition erlaubt der Produktion einer Berechnung, im Endwort allein verschlüsselt zu werden, wohingegen sonst die Produktion in der kompletten Folge von erzeugten Wörtern durch das Wiederholen der Anhängsel-Operation verschlüsselt würde.

Eine allgemeine alternative Definition verwendet kein stockendes Symbol und behandelt alle Wörter der Länge weniger als M als stockende Wörter. Eine andere Definition ist die ursprüngliche, die durch den Posten 1943 verwendet ist (beschrieben im historischen Zeichen unten), in dem das einzige stockende Wort die leere Schnur ist.

Beispiel: Eine einfache 2-Anhängsel-Illustration

Das soll ein einfaches 2-Anhängsel-System bloß illustrieren, das ein stockendes Symbol verwendet.

2-Anhängsel-System

Alphabet: {a, b, c, H}

Produktionsregeln:

a-> ccbaH

b-> cca

c-> Cc

Berechnung

Anfängliches Wort: Blöken

acca

caccbaH

ccbaHcc

baHcccc

Hcccccca (Halt).

</pre>

Beispiel: Berechnung von Folgen von Collatz

Dieses einfache 2-Anhängsel-System wird von [De Mol, 2008] angepasst. Es verwendet kein stockendes Symbol, aber hält auf jedem Wort der Länge weniger als 2, und schätzt eine ein bisschen modifizierte Version der Folge von Collatz.

In der ursprünglichen Folge von Collatz ist der Nachfolger von n irgendein n/2 (für sogar n) oder 3n + 1 (für sonderbaren n). Der Wert 3n + 1 ist klar sogar für sonderbaren n, folglich ist der folgende Begriff danach 3n + 1 sicher (3n + 1)/2. In der Folge, die durch das Anhängsel-System unten geschätzt ist, lassen wir diese Zwischenstufe aus, folglich ist der Nachfolger von n (3n + 1)/2 für sonderbaren n.

In diesem Anhängsel-System wird eine positive ganze Zahl n durch das Wort aa... mit dem n a's vertreten.

2-Anhängsel-System

Alphabet: {a, b, c}

Produktionsregeln:

a-> bc

b-> ein

c-> aaa

Berechnung

Anfängliches Wort: aaa

Alphabet

cbc

caaa

aaaaa

aaabc

abcbc

cbcbc

cbcaaa

caaaaaa

aaaaaaaa

aaaaaabc

aaaabcbc

aabcbcbc

bcbcbcbc

bcbcbca

bcbcaa

bcaaa

aaaa

aabc

bcbc

bca

aa

bc

a

(Halt)

</pre>

Turing-Vollständigkeit der M Anhängsel-Systeme

Für jeden m> 1 ist der Satz der M Anhängsel-Systeme Turing-abgeschlossen; d. h., für jeden m> 1, ist es der Fall, dass für jede gegebene Maschine von Turing T es eine M Anhängsel-System gibt, das T vortäuscht. Insbesondere ein 2-Anhängsel-System kann gebaut werden, um eine Universale Turing Maschine vorzutäuschen, wie von Wang 1963 und von Cocke & Minsky 1964 getan wurde.

Umgekehrt, wie man zeigen kann, ist eine Maschine von Turing eine Universale Turing Maschine durch den Beweis, dass sie eine Turing-ganze Klasse der M Anhängsel-Systeme vortäuschen kann. Zum Beispiel, Rogozhin 1996 hat die Allgemeinheit der Klasse von 2-Anhängsel-Systemen mit dem Alphabet {a..., a,} und entsprechende Produktion {aaW..., aaW, aa,} bewiesen, wo die W nichtleere Wörter sind; er hat dann die Allgemeinheit eines sehr kleinen (4-Staaten-, 6-Symbole-) Maschine von Turing bewiesen, indem er gezeigt hat, dass es diese Klasse von Anhängsel-Systemen vortäuschen kann.

Das stockende 2-Anhängsel-Problem

Diese Version des stockenden Problems ist unter den einfachsten, am meisten beschriebenen unentscheidbaren Entscheidungsproblemen:

In Anbetracht einer willkürlichen positiven ganzen Zahl n und einer Liste von n+1 willkürlichen Wörtern P, P..., P, Q auf dem Alphabet {1,2..., n}, tut wiederholte Anwendung der Anhängsel-Operation t: ijX  XP schließlich Bekehrter Q in ein Wort der Länge weniger als 2? D. h. die Folge Q, t (Q), t enden (Q), t (Q)...?

Historisches Zeichen auf der Definition des Anhängsel-Systems

Die obengenannte Definition unterscheidet sich von diesem des Postens 1943, dessen Anhängsel-Systeme kein stockendes Symbol verwenden, aber eher nur auf dem leeren Wort, mit der Anhängsel-Operation t hinken, wie folgt definiert werden:

• Wenn x das leftmost Symbol eines nichtleeren Wortes S anzeigt, dann ist t (S) die Operation, die aus dem Wort P (x) zum richtigen Ende von S und der leftmost M Symbole des Ergebnisses besteht - wenn es weniger gibt als M Symbole.

Die obengenannte Bemerkung bezüglich der Turing-Vollständigkeit des Satzes der M Anhängsel-Systeme, für jede M &gt; 1, gilt auch für diese Anhängsel-Systeme, wie ursprünglich definiert, durch den Posten.

Ursprung des Namens "Anhängsel"

Gemäß einem Kommentar im Posten 1943 hat B. P. Gill den Namen für eine frühere Variante des Problems vorgeschlagen, in dem die erste M Symbole unberührt, aber eher eine Markierung verlassen werden, die die aktuellen Positionsbewegungen nach rechts durch die M Symbole jeder Schritt anzeigt. Der Name für das Problem der Bestimmung, ob die Markierung jemals das Ende der Folge berührt, wurde dann das "Problem des Anhängsels" synchronisiert, sich auf das Spiel der Kinder des Anhängsels beziehend.

Zyklische Anhängsel-Systeme

Ein zyklisches Anhängsel-System ist eine Modifizierung des ursprünglichen Anhängsel-Systems. Das Alphabet besteht aus nur zwei Symbolen, 0 und 1, und die Produktionsregeln umfassen eine Liste der Produktion betrachtet folgend, zurück zum Anfang der Liste nach dem Betrachten der "letzten" Produktion auf der Liste Rad fahrend. Für jede Produktion wird das leftmost Symbol des Wortes untersucht — wenn das Symbol 1 ist, wird die aktuelle Produktion am richtigen Ende des Wortes angehangen; wenn das Symbol 0 ist, werden keine Charaktere am Wort angehangen; in jedem Fall wird das leftmost Symbol dann gelöscht. Das System hinkt, wenn und wenn das Wort leer wird.

Beispiel

Zyklisches Anhängsel-System

Produktion: (010, 000, 1111)

Berechnung

Anfängliches Wort: 11001

Produktionswort

------------------------

010 11001

000 1001010

1111 001010000

010 01010000

000 1010000

1111 010000000

010 10000000

..

..</pre>

Zyklische Anhängsel-Systeme wurden von Matthew Cook unter dem Verwenden von Stephen Wolfram geschaffen, und wurden in der Demonstration von Cook verwendet, dass die Regel 110 Zellautomat universal ist. Ein Schlüsselteil der Demonstration war, dass zyklische Anhängsel-Systeme mit einer Turing-ganzen Klasse von Anhängsel-Systemen wetteifern können.

Wetteifer von Anhängsel-Systemen durch zyklische Anhängsel-Systeme

Mit einer M Anhängsel-System mit dem Alphabet {a...,} und entsprechende Produktion {P..., P} wird durch ein zyklisches Anhängsel-System mit der m*n Produktion wettgeeifert (Q..., Q,-...,-), wo alle außer der ersten n Produktion die leere Schnur (angezeigt durch'') sind. Die Q sind encodings des jeweiligen P, der durch das Ersetzen jedes Symbols des Anhängsel-Systemalphabetes durch eine Länge-n binäre Schnur wie folgt erhalten ist (diese sollen auch auf das anfängliche Wort einer Anhängsel-Systemberechnung angewandt werden):

a =100... 00

a =010... 00

. . .

a =000... 01

D. h. verschlüsselt als eine binäre Schnur mit in der k Position vom links, und 's anderswohin zu sein. Aufeinander folgende Linien einer Anhängsel-Systemberechnung werden dann verschlüsselt als jede (m*n) Linie seines Wetteifers durch das zyklische Anhängsel-System vorkommen.

Beispiel

Das ist ein sehr kleines Beispiel, um die Wetteifer-Technik zu illustrieren.

2-Anhängsel-System

Produktionsregeln: (-> bb, b-> abH, H-> H)

Alphabet-Verschlüsselung: = 100, b = 010, H = 001

Produktion encodings: (bb = 010 010, abH = 100 010 001, H = 001)

Zyklisches Anhängsel-System

Produktion: (010 010, 100 010 001, 001,---)

Anhängsel-Systemberechnung

Anfängliches Wort: ba

abH

Hbb (Halt)

Zyklische Anhängsel-Systemberechnung

Anfängliches Wort: 010 100 (=ba)

Produktionswort

-----------------------------------------

* 010 010 010 100 (=ba)

100 010 001 10 100

001 0 100 100 010 001

- 100 100 010 001

- 00 100 010 001

- 0 100 010 001

* 010 010 100 010 001 (=abH)

100 010 001 00 010 001 010 010

001 0 010 001 010 010

- 010 001 010 010

- 10 001 010 010

- 0 001 010 010

* 010 010 wettgeeiferter Halt-> 001 010 010 (=Hbb)

100 010 001 01 010 010

001 1 010 010

- 010 010 001

......

</pre>

Jede sechste Linie (gekennzeichnet durch) erzeugt durch das zyklische Anhängsel-System ist die Verschlüsselung einer entsprechenden Linie der Anhängsel-Systemberechnung, bis der wettgeeiferte Halt erreicht wird.

Siehe auch

• Warteschlange-Automat
• Cocke, J., und Minsky, M.: "Allgemeinheit von Anhängsel-Systemen mit P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
• De Mol, L.: "Anhängsel-Systeme und Collatz ähnliche Funktionen", Theoretische Informatik, 390:1, 92-101, Januar 2008. (Vorabdruck Nr. 314.)
• Marvin Minsky 1961, Rekursive Unlösbarkeit des Problems des Postens "des Anhängsels" und der anderen Themen in der Theorie von Turing Maschinen", die Annalen der Mathematik, 2. ser. Vol. 74, Nr. 3. (November 1961), Seiten 437-455. Stabile URL-ADRESSE:

http://links.jstor.org/sici?sici=0003-486X%2819611%292%3A74%3A3%3C437%3ARUOPPO%3E2.0.CO%3B2-N.

• Marvin Minsky, 1967, Berechnung: Begrenzte und Unendliche Maschinen, Prentice-Hall, Inc. Englewoord Klippen, N.J. keine internationale Standardbuchnummer, Bibliothek der Kongress-Kartei Nummer 67-12342.

:: In einem Kapitel 14 betitelt "Sehr Einfache Basen für die Berechenbarkeit" präsentiert Minsky einen sehr lesbaren (und exampled) Paragraph 14.6 Das Problem "des Anhängsels" und der Monogenic Kanonischen Systeme (Seiten 267-273) (wird dieser Paragraph als "Anhängsel-System" mit einem Inhaltsverzeichnis versehen). Minsky verbindet seine Frustrierenerfahrungen mit dem allgemeinen Problem: "Posten hat das (00, 1101) Problem "unnachgiebig", und so ich sogar mit der Hilfe eines Computers gefunden." Er kommentiert, dass eine "wirksame Weise, für jede Schnur S zu entscheiden, ob sich dieser Prozess jemals, wenn angefangen, mit S wiederholen wird", unbekannt ist, obwohl einige spezifische Fälle unlösbar bewiesen worden sind. Insbesondere erwähnt er den Lehrsatz und Folgeerscheinung von Cocke 1964.

• Posten, E.: "Die formellen Verminderungen des kombinatorischen Entscheidungsproblems", amerikanische Zeitschrift der Mathematik, 65 (2), 197-215 (1943). (Anhängsel-Systeme werden auf p eingeführt. 203ff.)
• Rogozhin, Yu.: "Kleine Universale Turing Maschinen", Theoret. Comput. Sci. 168, 215-240, 1996.
• Wang, H.: "Anhängsel-Systeme und Zeitabstand-Systeme", Mathematik. Annalen 152, 65-74, 1963.

Außenverbindungen

http://mathworld.wolfram.com/TagSystem.html http://mathworld.wolfram.com/CyclicTagSystem.html

• http://www.wolframscience.com/nksonline/page-95 (zyklische Anhängsel-Systeme)
• http://www.wolframscience.com/nksonline/page-669 (Wetteifer von Anhängsel-Systemen)