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

deknos Permalink
April 18, 2012, 07:02

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

April 18, 2012, 15:51

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

Mog Permalink
April 18, 2012, 17:24

universal turing machine*
else the proof ain't a proof

r0p3_ Permalink
April 18, 2012, 17:42

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

April 24, 2012, 01:24

Awesome post, sed just got a lot cooler

August 07, 2013, 12:56

Awesome post. Thanks for share.....
I have a SEO worker group website. Please visit it and Replay me...
My site is SMITEXPERT || WORLD WIDE SEARCH ENGINE OTPTIMIZATION GROUP OF BANGLADESH http://smitexpert.com

September 21, 2013, 13:10

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

March 20, 2014, 02:33

Just want to say your article is as amazing. blog The clearness in your post is simply cool and i could assume you are an expert on this subject. Well with your permission let me to grab your feed to keep up to date with forthcoming post. Thanks a million and please carry on the enjoyable work

katherinebrunt Permalink
April 24, 2014, 13:38

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.

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the first letter of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.

Advertisements