ed(1) is Turing-Complete

Can a mere text editor be powerful enough to calculate anything that a computer can? Sure there’s Emacs, but it’s really just a Lisp interpreter, so it hardly counts. It turns out that even the humble line editor ed(1) is theoretically capable of such computation.

ed(1), or simply ed (the “(1)” comes from the man page section), is the standard text editor. It is the original Unix text editor and is the ancestor, either directly or indirectly, to many modern utilities, including sed, grep and vi. Unlike most editors today, ed is a line editor: instead of presenting the user with a screen full of text as a visual editor would, it uses commands to act on lines in a buffer.

A system that is Turing-complete is a system that can simulate any Turing machine, and a Turing machine is an abstract machine that can compute anything that can be computed with an algorithm (most programming languages are Turing-complete). To show that a system is Turing-complete, one only needs to show that it can simulate another Turing-complete system. Note that Turing completeness implies nothing about the efficiency of the system.

Rule 110 is an example of a Turing-complete system. It is an elementary cellular automaton (similar to Conway’s Game of Life, but in one dimension only) that was shown to be Turing-complete by Matthew Cook around 2000. As an elementary cellular automaton, the Rule defines the life of a cell in the next generation based on its current value and the values of the cells adjacent to it.

I had an idea one day: if you could call ed recursively, you’d be able to implement Rule 110 and prove that ed is Turing-complete.

So I got to work on it. It turns out, yes, it is possible to simulate Rule 110 in ed, showing that ed is Turing-complete.

Here it is, the code in full (as of writing), licensed under the MIT. Instructions on how to run the simulation can be found in the GitHub repository. An overview and a command-by-command walkthrough follows.

$a

.
-t.
.g/^\(.\).*\(.\)$/s//\2&\1/
.g/^.$/s//&&&/
s/./&\
/g
d
?^$?+,$-2g/^/+,+2t.\
-2,.j\
s/111/0/\
s/110/1/\
s/101/1/\
s/100/0/\
s/011/1/\
s/010/1/\
s/001/1/\
s/000/0/
$-,$d
?^$?,$jp
w
!exec ed '%' < '%'
q

# DATA
00000000000000000000000000000100

But before that, I’d like to thank Tom Ryder for sparking my interest in ed, and @ed1conf for reviewing the script and keeping my interest in ed high.

Explanation →

Advertisements

Press [Tab] to read ‘dreadnoughtsix’ introduction

Loading /introduction.....

 

Loading /authorname...............................ready.

Boot complete!

Greetings!

Allow me to introduce myself. I am Dreadnought Six. I was the former administrator for the somewhat popular tech blog named Tech Gum. I currently write freelance in my personal yet nonexclusive blog called the Unfinished Basement.

To many, I am a friend. To some, I am a foe. To only but a few, I am a brother. But to one, and one only, I am a lover.

I am currently a first year Computer Science student, and rightfully so, I am lazy (which is probably why you’re seeing this post on Christmas Eve). I am a devoted born again Christian, a professional League of Legends practitioner, and a 5-time Pokemon Master (captured: 652). I’ve been a Windows user my entire life, with a small part of my life (I namely called the ‘iDark Ages’) liking the Apple brand. The main author of this blog, tPenguinLTG, is a close friend of mine (you decide) and as he so desperately needed to, introduced me to the world of Computer Science (seriously, I was suppose to be chef) and to the world of Linux.

The only way to deal with an unfree world is to become so absolutely free that your very existence is an act of rebellion.

– Albert Camus

I find a sense of freedom in Linux, which is why I’ve decide to take the leap of faith. I’m not yet entirely engrossing myself into the operating system which means I’ll still have my Windows 7 partition. I’ve decided long before this blog existed, that I’d install Linux Mint. Alas, I’ve seen a new operating system named CrunchBang (#!), to which I fell in love with the moment I saw it.

Follow my blog the Unfinished Basement, or else.

Cheers!