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

SSH remote port forwarding without server support

You read about how to create an SSH tunnel and saw that you can do the same in reverse, forwarding a port from the server to your local machine. You tried it out on a server you have access to and discovered that the port you chose isn’t opening on the outside, even though the port is allowed through the firewall. What gives?

A visual representation of remote port forwarding

SSH Remote Port Forwarding flow diagram

Continue reading

Package Management Systems Explained

Any Linux user should be familiar with package management systems. After all, they are a key component of every Linux distro.

Package management systems are an effective way to organize packages for installation, upgrade and deletion.

Package management systems have three sub-components: repositories, packages and package managers. A repository is a database of packages that users can search, download and install. A package contains the files for a particular program along with metadata that includes the package’s name, size and dependencies. When a user wants to install a package, the package manager will automatically search the repositories and install any missing dependencies.

As a user of Linux Mint, the package manager I’m familiar with is APT/dpkg through Synaptic. While I have no experience using existing elements to integrate into my own programming, I can comment on the advantages and disadvantages that a package management system for a Windows-adapted user.

Advantages

1) Easy installation, upgrade and deletion.

One of the most annoying parts about installing, upgrading or deleting anything on Windows is browsing through all the different options available and figuring out which programs go hand-in-hand with one another.

Continue reading

Command Explained: “Look Busy On *nix”

Here’s a command that I posted on my main blog last year. Open a terminal and give it a try (stop it with Ctrl+C)!
$ cat /dev/urandom | hexdump -C | grep "34 32"

`The Penguin' says...

I recently posted a command to “Look Busy On *nix“:
$ cat /dev/urandom | hexdump -C | grep "34 32"

If you ran it, you console/terminal screen should have been filled with lines like these:

I will break apart the command and explain what it actually did.

$
Indicates that this command should be run as a regular user (i.e. without root privileges). This isn’t actually part of the command and shouldn’t be included when typing it into the shell.
cat
Output the contents of the specified file(s) to stdout.
/dev/urandom
The file from which to read. /dev/urandom is a special file that acts as a pseudo-random number generator.
|
Redirects or “pipes” the output of the previous command into the input of the next command (stdout to stdin).
hexdump
Outputs a hexdump of the specified file, or stdin if no file specified.
-C
From the man page:

View original post 91 more words

Linux Distros: What are the differences and how do I choose one?

Linux distro stickers

Ask a newcomer about Linux and they’ll probably mention something about Ubuntu. Someone a little more knowledgeable about Linux will know that there are many flavours, called “distributions” (or “distros”, for short), of Linux. There are over six hundred distributions out there, and they’re all labelled as “Linux”. What makes one distro different from the next, and how do you choose one?
Continue reading