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?

December 17, 2014, 06:06

Hello everyone,
thanks for sharing this informative blog with us for more informative essay,assignment,dissertation,thesis etc.. Visit www.essayprime.com services.

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

September 21, 2013, 13:10

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

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.

Kira Permalink
July 30, 2014, 15:33

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

October 08, 2014, 09:29

Very nice and informative sharing. I work for Finance Assignment writing service. And it is also very helpful for student to do their assignment.

Garry Mann Permalink
October 09, 2014, 12:23

Nice material, thanks for sharing. If you often say I need help writing an essay, go to the site and get it.

November 12, 2014, 08:13

Informative post described by the writer. Thanks for share this blog.
Dissertation Editing Services UK offered by Dissertation Prime

November 12, 2014, 08:18

Excellent blog. Very interesting and informative blog posted by the author.
BestEssay Writing Help UK provides by Essay Prime

Thanks for sharing the information which I believe never heard before and will sure help me to explore some awesome new things for me.

December 01, 2014, 07:43

Where to look for the best content within the most affordable prices? Only the best writing service will cater to all your academic needs!

December 01, 2014, 09:37

God helps those who help themselves, but we are here for those who cannot even help their own selves while writing their essays or projects.

December 01, 2014, 09:37

God helps those who help themselves, but we are here for those who cannot even help their own selves while writing their essays or projects.

December 02, 2014, 07:45

It's a very helpful post about text filtering program.

Alice Scarlet Permalink
December 03, 2014, 05:39

finance assignment Now since any programming language that can implement a Turing machine is Turing complete leads us to conclude that sed is also Turing complete.

Diana Permalink
December 17, 2014, 16:43

This article is quite helpful and informative too. I enjoyed a lot. Thanks for sharing such a great article.

Beautiful Christmas Quotes for your friends and family...
christmas quotes
Christmas Messages for Whatsapp

Best Christmas Greetings for your friends and family...
christmas greeting
christmas wishes

What to Write in Christmas Card....... Check out best Christmas Greeting Card Words
What to Write in Christmas Card

Get Beautiful and Unique Christmas Wallpapers for free
free christmas wallpaper
christmas tree decorating ideas

Thanks for sharing such a great article.

Leave a new comment

(why do I need your e-mail?)

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

Type the word "unix_186": (just to make sure you're a human)

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

Advertisements