Turing-Maschine mit sed

Eine wenig bekannte Tatsache ist, dass sed berechnungsvollständig ist. Der Beweis geschieht durch Konstruktion einer Turing-Maschine in sed.

Das folgende script turing.sed generiert aus einer Datei, welche die Regeln der Turingmaschine beschreibt, ein weiteres sed-script, welches die Turing-Maschine implementiert:

1 i \
:1\
p
s/^\([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \(left\)/# rule \1 \2 \3 \4 \5\
s\/^\1:\\([ a-zA-Z0-9_]*\\) \\([a-zA-Z0-9_]*\\)\\[\\(\2\\)\\]\/\3:\\1[\\2]\4 \/\
t 1\
s\/^\1:[ ]*\\[\2\\][ ]*\/\3:[_]\4 \/\
t 1\
/
t
s/^\([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\) \(right\)/# rule \1 \2 \3 \4 \5\
s\/^\1:\\([ a-zA-Z0-9_]*\\)\\[\2\\]\\([a-zA-Z0-9_][a-zA-Z0-9_]*\\)[ ]*\/\3:\\1 \4[\\2]\/\
t 1\
s\/^\1:\\([ a-zA-Z0-9_]*\\)\\[\2\\][ ]*\/\3:\\1 \4[_]\/\
t 1\
/

Die Regeldatei besteht aus einer oder mehreren Zeilen der Form:

current_state current_symbol new_state new_symbol move_direction

Dabei sind current_state, current_symbol, new_state, new_symbol beliebige, aus den Zeichen 0-9, A-Z, a-z und _ (underscore) bestehende Zeichenketten und bezeichnen den momentanen Zustand bzw. das momentane Symbol, welche die Vorbedingung der Regel darstellen, respektive den neuen Zustand, in den die Maschine übergeht und das zu schreibende Zeichen. move_direction ist entweder left oder right und bezeichnet die Richtung, in welcher der Schreib-/Lesekopf über das Band nach Zustandsübergang bewegt werden soll. Die Turing-Maschine stoppt, sobald ein Zustand und ein Symbol auftreten, fü welche in der Regeldatei keine Übergangsregel definiert ist.

Der Zustand der Maschine und des Bandes wird durch Zeichenketten der Form

machine_state: symbol1 symbol2 symbol3[symbol4]symbol5 symbol6
wobei die aktuelle Position des Kopfes durch [] gekennzeichnet wird. Per Konvention wird durch einen einfachen _ (underscore) ein leeres Feld auf dem Band bezeichnet; bei Bedarf wird das Band automatisch durch leere Felder nach rechts oder links erweitert.

Beispiel

Aus der Regeldatei inc.rules

incr 0 stop 1 right
incr 1 incr 0 left
incr _ stop 1 right
wird durch Aufruf von sed -f turing.sed <inc.rules >inc.sed:
:1
p
# rule incr 0 stop 1 right
s/^incr:\([ a-zA-Z0-9_]*\)\[0\]\([a-zA-Z0-9_][a-zA-Z0-9_]*\)[ ]*/stop:\1 1[\2]/
t 1
s/^incr:\([ a-zA-Z0-9_]*\)\[0\][ ]*/stop:\1 1[_]/
t 1
 
# rule incr 1 incr 0 left
s/^incr:\([ a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\)\[\(1\)\]/incr:\1[\2]0 /
t 1
s/^incr:[ ]*\[1\][ ]*/incr:[_]0 /
t 1
 
# rule incr _ stop 1 right
s/^incr:\([ a-zA-Z0-9_]*\)\[_\]\([a-zA-Z0-9_][a-zA-Z0-9_]*\)[ ]*/stop:\1 1[\2]/
t 1
s/^incr:\([ a-zA-Z0-9_]*\)\[_\][ ]*/stop:\1 1[_]/
t 1
Mittels echo "incr: 1 1 0 1[1]" | sed -n -f inc.sed wird diese Turing-Maschine auf ein Beispielproblem angewandt:
incr: 1 1 0 1[1]
incr: 1 1 0[1]0
incr: 1 1[0]0 0
stop: 1 1 1[0]0