Beispiele

unaryplusone.txt

#tape 1111
 
# Addiert 1 zu einer unären zahl
# Die Maschine stoppt am Anfang der Zahl.
 
 
# Vorwärts bis zum ersten . Schreibe dort eine 1, gehe nach links und mache fertig
start
  . 1 L fertig
 
# Rückwärts bis zum ersten . Dann rechts und stop.
fertig L
  . . R stop

bla.txt

# Schreibt bla ;-)
 
# {...} Beinhaltet Kommandos der Form Px, um den Buchstaben x zu schreiben, oder R,L, um den Kopf zu bewegen.
# Damit werden eine ganze Reihe von Zuständen generiert.
start
   . {Pb R Pl R Pa L L} stop
 

Folgende Zeichen dürfen nicht als Symbole auf dem Band verwendet werden:

• Leerzeichen (Trennsymbol)
• . Blank
• * (wildcard)
• @ (Symbolvariable in m-Funktion oder m-Aufruf)
• \$ (Zustandsvariable)
• [ und ] (Symbolbereich)
• _ (underscore, wird intern verwendet)
• # Beginn eines Kommentars

• Zeilen, die mit # beginnen sind Kommentar, ausser nach #tape folgen die Symbole, die beim Start auf dem Band geschrieben sind.

• Die Zustände sind durch eine Leerzeile getrennt.
• Der default ist das Zeichen lassen und nach rechts gehen. Die default-Richtung kann nach dem Zustandsnamen angegeben werden. Danach kann zusätzlich ein default-Zustand angegeben werden (wenn von diesem verschieden).
• Für ein Zeichen read kann in einem Zustand folgendes definiert werden:
  • read write dir state, wobei dir auch 'N' für nicht bewegen sein kann.
  • read {c1 c2 …} state, wobei c1, c2 etc. Kommandos 'R' für rechts, 'L' für links und 'Px' für ein x aufs Band schreiben ist.
• Es ist möglich, für read einen Bereich von Zeichen mit [xyz] anzugeben (nur Symbolen, keine @1 etc.), oder * für alle möglichen Zeichen.
• Wird für write ein * verwendet bezieht sich das auf das gelesene Zeichen.

• Header: @name(x ; y )
  • wobei x die Anzahl der zu übergebenden Symbole als Argumente ist und
  • y die Anzahl der zu übergebenden Zustände ist.
• Body: Menge von lokalen Zustandsdefinitionen. Diese können @1, @2, etc. als übergebene Symbole und $1, $2 als übergebene Zustände enthalten.
  • Die Zustände sollten global eindeutige Namen haben (ausser Sie werden nur lokal in der m-Funktion verwendet).
  • Typischerweise wird ein Zustand übergeben, zu dem die Funktion «zurückkehren» soll, wenn sie fertig ist.
• Footer: @end

Slides vom Turing-Maschinen-Kurs der Uni Fribourg