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

# State 1
1  L2

# State 2
2 1R3

# State 3
3  RF

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

$ sed -f turing.sed <

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:


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!

I was reading about vim the other day and found out why it used hjkl keys as arrow keys. When Bill Joy created the vi text editor he used the ADM-3A terminal, which had the arrows on hjkl keys. Naturally he reused the same keys and the rest is history!

Here is how the hjkl keys looked:

ADM-3A keyboard's hjkl keys with arrows.

And here is the whole terminal that vi was created on:

Lear Siegler's ADM-3A computer terminal.

Since vim is derived from vi, it uses the same hjkl keys.

And while we're at it, notice where the ESC key is positioned:

Lear Siegler's ADM-3A computer terminal's full keyboard.

That's why the ESC is used to change between vi modes! Because it's so close and easy to reach.

Also ever wondered why home directory is ~ in UNIX? Look at the HOME key in upper right corner!

HJKL T-Shirt!

Update: No longer available.

I just got a deal with Teespring for a hjkl t-shirt! Teespring is like kickstarter for t-shirts. If at least 15 people commit to buy the shirt the deal goes through and everyone gets the shirt. Otherwise nothing happens.

Get your limited edition hjkl t-shirt now! (Ships worldwide in 4-8 days.)

Extra Discussions!

My post has generated a lot of awesome responses, see hacker news, osnews, and reddit discussions (two of them on /r/programming and /r/vim).

Follow me!

If you enjoyed my post, subscribe to my blog, follow me on twitter, google+ or github. Thank you!

We're super excited to announce dedicated plans for Browserling. With a dedicated Browserling plan you get your own Windows server with all the browsers pre-installed, plus you can install any software that you want, any browser plugins you want, and do absolutely anything you wish with it as you also get full administrator rights to your server.

I made a demo video of dedicated plans. Take a look:

Tweet us @browserling if you want to try a free demo. Or you can just buy a dedicated instance right away from the pricing menu!

Browserling is an interactive cross-browser testing tool. You can use it to test your website in IE, Firefox, Chrome, Opera, and Safari.

Hello ladies and gentlemen! I'm happy to announce my 3rd e-book called "Perl One-Liners Explained." This book is based on the "Perl One-Liners Explained" article series that I wrote over the last 3 years and that has been read over 500,000 times!

I went through all the one-liners in the article series, improved explanations, fixed mistakes and typos, added a bunch of new one-liners, added an introduction to Perl one-liners and a new chapter on Perl's special variables.

Table of Contents

The e-book has 111 pages and it explains 130 unique one-liners. Many of one-liners are presented in several different ways so the total number of one-liners in the book is over 200.

The e-book is divided into the following chapters:

  • Preface.
  • 1. Introduction to Perl One-Liners.
  • 2. Spacing.
  • 3. Numbering.
  • 4. Calculations
  • 5. String Creation and Array Creation.
  • 6. Text Conversion and Substitution.
  • 7. Selective Printing and Deleting of Lines.
  • 8. Handy Regular Expressions.
  • 9. perl1line.txt
  • Appendix A. Perl's Special Variables.
  • Index.

What are Perl One-Liners?

Perl one-liners are small and awesome Perl programs that fit in a single line of code and they do one thing really well. These things include changing line spacing, numbering lines, doing calculations, converting and substituting text, deleting and printing certain lines, parsing logs, editing files in-place, doing statistics, carrying out system administration tasks, updating a bunch of files at once, and many more.

Let's take a look at several practical examples that you can easily do with one-liners. All these examples and many more are explained in the e-book.

I have also made the first chapter of the book, Introduction to Perl One-Liners, freely available. Please download the e-book preview to read it.

Example 1: Replace a string in multiple files at once

perl -p -i.bak -e 's/Config/config/g' conf1 conf2 conf3

Suppose you have 3 configuration files, and you discover that you made a mistake and need to replace all occurrences of Config with config. This one-liner does just that. It executes the s/Config/config/g that replaces all occurrences of Config with config on all lines. And since you're smart about it, you always do -i.bak to make backup files in case something goes wrong.

I explain the -i, -p, and -e arguments in the e-book in great detail.

Example 2: Generate a random 8 character password

perl -le 'print map { ("a".."z")[rand 26] } 1..8'

This one-liner generates and prints a random 8 character password. It uses the list range operator .. operator to produce all strings from "a" to "z", which is the alphabet. Then a random letter is chosen by rand 26 and this operation is repeated 8 times.

Example 3: URL-escape a string

perl -MURI::Escape -lne 'print uri_escape($string)'

Here we use the URI::Escape module from CPAN. It exports the uri_escape function that does URL-escaping.

You can install this module from CPAN by running perl -MCPAN -e'install URI::Escape' on the command line.

I have this one-liner as an alias actually for both URL-escaping and unescaping URL-escaping as it's such a common thing to do:

urlescape () { perl -MURI::Escape -lne 'print uri_escape($_)' <<< "$1" }
urlunescape () { perl -MURI::Escape -lne 'print uri_unescape($_)' <<< "$1"; }

Then I can do this in the shell:

$ urlescape ""

$ urlunescape

Very useful!

Example 4: Print all lines from line 17 to line 30

perl -ne 'print if 17..30'

Here we use the binary flip-flop operator .. that becomes true when the input line number is 17, stays true while the line number is less than or equal to 30, and then becomes false. Combining the flip-flop operator with print if makes it print only lines 17-30.

Example 5: Remove all consecutive blank lines, leaving just one

perl -00pe0

I included this one-liner here in the examples just to show you how funny and obscure one-liners can get. This one-liner deletes all repeated blank lines from the input or from the given file. It does it by enabling the paragraph slurp mode through -00 command line argument, which reads the input paragraph-by-paragraph, rather than line-by-line, and prints the paragraphs. This way any number of blank lines between the paragraphs get ignored.

I explain this one-liner in more details in the e-book.

As I hope you can see, knowing how to write one-liners is very useful. It was one of my top priority tasks through the years to become very efficient in the shell. Literally every day when I'm programming, I have to do all kinds of data processing tasks, changing files, verifying output, doing quick calculations, parsing data, etc, and knowing Perl one-liners makes it really fast to get things done.

Now that I have written this e-book, you can become very efficient, too. Enjoy!

Book Preview

I prepared a free book preview that contains the first 13 pages of the book. It includes the table of contents, preface, introduction to Perl one-liners and the first page of the second chapter.

Buy it now!

The price of the e-book is $9.95 and it can be purchased via PayPal:

PayPal - The safer, easier way to pay online!

After you have made the payment, my automated e-book processing system will send you the PDF e-book in a few minutes!

Tweet about my book!

Help me spread the word about my new book! I prepared a special link that you can use to tweet about it:

What's next?

I really love writing about programming and I have planned writing many more books. The next few are going to be a book on mastering vim, a practical guide on how to be anonymous on the web, and the catonmat book.


Enjoy the book and don't forget to leave comments about it! Ask me anything you wish and I'll help you out.

Also if you're interested, take a look at my other two e-books. The 1st one is called "Awk One-Liners Explained" and the 2nd one is called "Sed One-Liners Explained" They're written in a similar style as this e-book and they teach practical Awk and Sed through many examples.

Finally, if you enjoy my writing, you can subscribe to my blog, follow me on Twitter or Google+.

Art by James Halliday.

1. We run the browsers on our servers.
2. You use the browsers from the graphical web console.
3. If the servers are full, you wait in the queue.

Try Browserling!