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

you post really help me a lot, thank you very much.

this is a very good source for improving websites and other social forums. i work for Assignment Box, an online platform from where students can buy UK assignment online. let me know if this code source can help us improve our online portal.

This was really very interesting. essay help - http://www.assignmentmasters.co.uk/essay/ I really have enjoyed this great website.

thank you very much.

thank you very much.

Jpbidding is the all-round deputy & export company from Japan.We take the hassle out of buying, contact to seller, packing, and shipping. We provide yahoo auction agency,japan shopping service and so on.

yahoo japan bidding:http://www.jpbidding.com/

yahoo japan auction agency:http://www.jpbidding.com/

yahoo auction agency:http://www.jpbidding.com/

## Leave a new comment