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!

Last week I got a chance to try Clickatell's Communicator 2 service. Communicator 2 is a browser-based SMS text messaging service. With this service you can send and receive messages from your browser.

To get started, you'll first need to create an account at Clickatell. You can do it here. You can choose between 6 plans currently - International, USA only, South Africa only, India only, Ireland only, United Kingdom only. Unfortunately the International plan excludes the USA, so to send messages both internationally and in the USA you'll need to get two plans.

I chose the USA-only plan, which goes for $9.95 a month and includes a two-way number and 500 messaging credits. The two-way number means that you get your own US phone number, which you can send and receive messages from. Each message costs 1 credit, so you can send 500 messages a month with this plan.

Signing up was as straightforward as filling a form with several fields that ask for name, surname, email and password. After you confirm the payment you'll get setup with the plan of your choice and you'll be all ready to go.


After you sign up you get your own phone number.

Sending messages is really easy. You just go to Messages section and you'll be presented with a dialog that asks for the number and the message. I sent myself a message to 14154258068 and it worked nicely.


Make sure to prefix the number with 1 if sending within USA.

Once you've entered the message and the number, you'll have a chance to review the message and you'll need to confirm it before it gets sent.


You'll have a chance to review the message in the confirmation page.

As with most products, there is always room for a little bit of improvement. With Clickatell's Communicator 2, I found the country code prefix to be a bit cumbersome. It turns out you always have to prefix the number with the country code as it's impossible to tell where you want your message to be sent. Possibly a small, user-friendly note/reminder that is easily visible would be helpful.

After you send the message, you'll get 1 credit deducted from your balance. The balance can always be seen in the upper right corner of the site, which is very convenient.


Each message costs 1 credit.

Receiving messages is very simple, too. Just go to the Inbox section of the site, and you'll see all the messages that have been sent to your two-way number. Receiving messages doesn't cost any credits.


The received messages are in Inbox.

Here is the summary of the all the features that Communicator 2 supports:

  • Import and manage contacts and distribution lists.
  • Create message templates and personalize your messages.
  • Monitor, track and analyze your messaging campaigns.
  • Automatically forward inbound replies to your email address or mobile device.
  • Send batches of messages directly from CSV files.

Overall I enjoyed this product and I definitely see myself using it for batch messaging and sending quick messages to friends as typing them out on the phone is time consuming.

Disclosure of Material Connection

I received one or more of the products or services mentioned above for free in the hope that I would mention it on my blog. Regardless, I only recommend products or services I use personally and believe my readers will enjoy. I am disclosing this in accordance with the Federal Trade Commission's 16 CFR, Part 255: "Guides Concerning the Use of Endorsements and Testimonials in Advertising."

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!

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 "Famous 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 "http://www.catonmat.net"
http%3A%2F%2Fwww.catonmat.net

$ urlunescape http%3A%2F%2Fwww.catonmat.net
http://www.catonmat.net

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!

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+.