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.

I have a hunch that if calling itself recursively using `!ed % < %` is allowed, then one might be able to prove that ed(1) is #TuringComplete by implementing #Rule110.

— tPenguinLTG (@tpenguinltg) March 6, 2018

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.

Pages: 1 2 3

Taming your Temporary Files

I don’t know about you, but there have been many times when I wanted to download something only temporarily with the intent to delete it later, like saving an image to upload elsewhere or saving email attachments that I didn’t need to keep to open in an external program. There have also been times when I wanted to test something out and had to temporarily create files with the intent to delete them later, whether it’s creating a test program, extracting a compressed archive, or even creating a named pipe (FIFO). I used to use my disk for that, using a ~/tmp directory, but it would slowly fill up when I neglected to delete these temporary files, thinking that they “might be useful later”; even to this day, I still have about 12GB of supposedly “temporary” files.

The largest files and folders in my tmp folder. Sorry, but I’m not going to show you my files!

How do you prevent these temporary files from filling up your disk? The obvious answer is to just delete them, and good for you if that works for you, but it evidently doesn’t work for me. You could stop downloading things or generating temporary files, but that’s unreasonable. One solution that I came up with when I used to run on Windows was to create a fixed-size container and put my temporary files there. I now had a maximum size for my temporary files so they wouldn’t overrun my disk. It worked for a while, but I made the mistake of making the container too small (only 256 MB), so in time, I was putting my larger temporary files in a tmp directory outside my container. I was also still not really deleting my temporary files, so in time, the container filled up.

So space-boxing the files is a good thing, but how do you make sure that your temporary files stay temporary and actually get deleted?

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?

SSH Remote Port Forwarding flow diagram

Are you sure you want to use Arch Linux?

All four authors here on *nix Windows are either using Arch Linux or have expressed an interest in trying it out. As a regular Arch user myself, I think Arch Linux is a great distro and I highly recommend it for anyone who wants to try it out. However, just like with any other distro, Arch might be less suitable than others for certain use cases.

Seasons Greetings From Linux!

It’s that time of year again! The time when we go around when we go around doing last-minute shopping, spend time with friends and family, and remember Christ’s birth.

Programs tend to be more or less the same all year round, but a couple of them change depending on the time of year, especially for Christmas.

VLC

From December 18 to January 1, VLC media player‘s striped orange cone sports a Santa hat.

VLC media Christmas icon

What’s the “Super” key?

If you’ve ever tried to configure your keyboard shortcuts, you may have come across something called the Super key. If you look on your keyboard, there’s probably no key labelled “Super“. So, what is it?

That’s Super Tux, alright.

Good riddance to PulseAudio! (or “Settling on a Linux sound server”)

I have a love-hate relationship with PulseAudio: it has a lot of great features, but sometimes it’s more resource-hungry than I would like, and it also crashes more often than I’d like. Actually, the only reason why I got PulseAudio was because Skype 4.3.0.37 required Pulse and dropped ALSA support; I would have stayed with plain ALSA had it not been for Skype (on that note, I really hate Skype, for more reasons than one).

PulseAudio

Move and resize windows from anywhere

Move this window. Go ahead, I’ll wait. Great. Now resize this window.

If you’re like most people, you moved the window by dragging the title bar and resized by dragging the edge or corner of the window. That works and all, but you have to move your mouse to the right spots, which may very well be at the opposite end of the screen, and what do you do if you find yourself with a title bar past the top of your screen?

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?

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?