Follow me on Twitter for my latest adventures!

Many people are surprised when they hear that sed is Turing complete. How come a text filtering program is Turing complete they ask? Turns out sed is like a small assembly language that has a comparison operation, a branching operation and a temporary buffer. If you translate a problem into a textual representation then these operations are enough to make sed Turing complete!

I didn't want to invent a new proof so I'll just present a proof by Christophe Blaess. The proof may sound silly but it works. Back in the day Christophe wrote an implementation of a Turing machine in sed [download turing.sed]. Now since any programming language that can implement a Turing machine is Turing complete leads us to conclude that sed is also Turing complete. ■ Haha. That's it!

Christophe Blaess offers his own introduction to Turing machines and a description of how his sed implementation works in his article Implementation of a Turing Machine as Sed Script.

Here is an example program for his Turing machine that increments a binary number. The program has the initial tape configuration on the first line of the program, and the program itself below it. In this example the initial tape configuration is the binary number `10010111`

(151) and the program increments it by one.

| 10010111 # State 0 0 R0 011R1 000R1 # State 1 1 L2 100R1 111R1 # State 2 2 1R3 201R3 210L2 # State 3 3 RF 300R3 311R3

To run this program save it to a file increment.tm and run it through turing.sed as following:

$ sed -f turing.sed < example.tm

You'll get the following output:

(0) | |10010111 (0) |1|0010111 (1) 1|0|010111 (1) 10|0|10111 (1) 100|1|0111 (1) 1001|0|111 (1) 10010|1|11 (1) 100101|1|1 (1) 1001011|1| (1) 10010111| | (2) 1001011|1| (2) 100101|1|0 (2) 10010|1|00 (2) 1001|0|000 (3) 10011|0|00 (3) 100110|0|0 (3) 1001100|0| (3) 10011000| | (F) 10011000 | | Final state F reached... end of processing

The output shows the state and tape changes as the program is executed. When it's done the final state `F`

is reached and the computation process terminates producing `10011000`

(152) as a result as expected.

Since you can write any program in sed, people have done so and written tetris, sokoban and many other programs. Take a look at these:

Impressive!

## The Busy Beaver

If you liked this article, you'll also like my article about the busy beaver. The busy beaver is a Turing machine that puts 1's on an initially blank tape. The busy beaver problem is to find an n-state Turing machine that puts as many 1's on the tape as possible. It hasn't been solved for a 5-state Turing machine yet and theorists doubt that it shall ever be computed for 6 states!

## My sed book

I wrote this fun book on sed a while ago called "Sed One-Liners Explained." If you don't know sed yet and wish to learn it, my book teaches it through 100 practical and well-explained examples. Take a look!

## Comments

hello,

there's a master thesis about turing completeness a few years before. It's from Matthias Benkmann of the "Ludwig Maximilian Universitaet" (short: LMU) in Munich.

Greets

I can't find it. Can you link it?

universal turing machine*

else the proof ain't a proof

it's enough to emulate a turing machine to be turing complete

Awesome post, sed just got a lot cooler

## Leave a new comment