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.
Aus der Regeldatei inc.rules
incr 0 stop 1 right incr 1 incr 0 left incr _ stop 1 rightwird 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 1Mittels 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