Thema: Tag-Systeme und zyklische Tag-Systeme

Berichterstatter/in: Günter Rote

Nachtrag:

• Universalität von Tag-Systemen:
  Cocke, John; Minsky, Marvin (1964). "Universality of Tag Systems with P=2". J. Assoc. Comput. Mach. 11: 15–20. doi:10.1145/321203.321206.
  Deletion number P = 2.
• Universalität von zyklischen Tag-Systemen:
  Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110.
  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, volume 4051 of Lecture Notes in Computer Science, pages 132–143, Berlin, Heidelberg, 2006. Springer. doi:10.1007/11786986_13. Siehe auch https://dna.hamilton.ie/assets/dw/NearyWoodsBCRI-04-06.pdf.

Zielfragen:

• Was passiert bei der Emulation durch die Turingmaschine, wenn das zyklische Tag-System terminiert?
• Wie stark wird die Eingabe der Turingmaschine bei der Emulation aufgeblasen?

Smith, ab S. 4

Es gibt einen Simulator für Turingmaschinen: https://turingmachinesimulator.com/

Einige Perl-Programme aus der Arbeit von Alex Smith (ab S. 26) sind unter Ressourcen abgespeichert. Vorschläge

• Lassen Sie perl sys0-3.pl 3 V 0A001122112200 und perl sys0-3.pl 2 V 0A001122112200 laufen, stellen Sie die Ausgaben nebeneinander, und vergleichen Sie. Eventuell auch ohne die V-Option.
• Lassen Sie perl sys0-3.pl 1 V 0A001122112200 und perl sys0-3.pl 2 V 0A001122112200 laufen, stellen Sie die Ausgaben nebeneinander, und vergleichen Sie.

ab Lemma 1, Punkt 2

ab Lemma 1, Induktionsschritt

Ab Induktionsschritt für Methode 2

ab Conjecture 4

"Why the initial condition works" auf Seite 12.

Aufgetretene Fragen:

• Bleibt die Eigenschaft, dass die Blöcke der Länge 2^w durch Zweien begrenzt sind (von denen manche zeitweilig durch Nullen ersetzt sein können), im Lauf der Simulation erhalten? (Mit anderen Worten, handelt es sich um eine Darstellung der Ausgangssituation oder um eine Invariante? (Die Überschrift heißt Initial condition / Condition during execution.)
• Was ist "end of the system 3 initial condition"? (Wo danach eine einzelne 1 angehängt wird.) Das Band von System 4 ist doch unendlich!
• Warum wird die 1 in Zustand C erreicht?
• Wie hängt der Parameter w genau mit der Anzahl an Schritten zusammen, die man in System 4 machen möchte.
• Was ist mit x ("the number of 0s in this region of the tape") auf S. 11 oben genau gemeint?

ab S.14, Punkt 3.

weiter ab S.16, vorletzter Absatz ("steps 2 and 3")

weiter ab S.16, vorletzter Absatz ("steps 2 and 3")