» About     » Archive     » Cast     » Authors     » Submit     » Search     » Random     » Statistics     » Forum     » FAQ     » Video Game     » RSS Feed     Updates daily

No. 192:

First | Previous | 2009-06-17 | Next | Latest

First | Previous | 2009-06-17 | Next | Latest

Permanent URL: https://mezzacotta.net/postcard/?comic=192

Translated from ancient Sumerian by: Chris Mann

The author writes:

You know, when I commented that there's a lot to be said about Turing machines, I didn't actually expect that people would expect me to be the one to say it. Still, you all emailed me, so I came up with another Turing joke to justify this little lesson.

Imagine you have a strip of paper that stretches out to infinity both to your left and to your right. The paper is divided into boxes along its length, and while almost all of the boxes are blank, there are a finite (maybe zero) number of them that each contain a single symbol from a predefined alphabet. All of these symbols are pencilled in, so they can be erased and rewritten at will.

You're standing in front of this strip, armed with a pencil, an eraser, and a book. The pencil, eraser, and for that matter the paper itself are all designed so that you can keep on erasing and writing symbols without wearing them out. Before you go and scribble on the paper willy-nilly, though, I should let you know - there are rules.

• Rule number 1: You are only allowed to read, erase and write in one square at a time.
• Rule number 2: You are only allowed to read, erase and write in a square according to the instructions written in the book.

I guess I should tell you about this book. Written in this book are instructions regarding what to do with the current square, depending on the symbol currently written in it. In fact, every page of the book has exactly one instruction for each symbol in the alphabet - including the blank symbol, meaning that for each symbol there are actually as many different instructions as there are pages in the book.

• Rule number 3: You are to follow the instructions according to the current page the book is open at, and you can only turn the page as the instructions allow.

The instructions look a bit like this:

IF the current square contains symbol number 3, THEN erase the symbol and WRITE symbol number 5 in the current square, MOVE one square to the left, and TURN this book to page 8.

The last page of the book is different to the others. Instead of having a list of different instructions, it has just one word: HALT. If you turn to this page, you stop processing the strip of paper.

When you process the strip, you start with the book open to page 1 and you get told which square you should process first. You then have to follow the instructions in the book until you turn to the last page. Obviously many different things could happen depending on the instructions in the book and the initial set of symbols written on the tape, so to get a feel for how it works let's try a simple example. In our alphabet, we'll have only one symbol other than the blank, which we'll designate as '1'. And our book will contain just 2 pages, which read as follows:

Page 1

IF the current square is blank, THEN WRITE a blank in the current square, MOVE one square to the right, and TURN this book to page 2.

IF the current square contains a 1, THEN erase it and WRITE a blank in the current square, MOVE one square to the right, and TURN this book to page 1.

Page 2

HALT

Now let's give you a strip of paper for you to process. There will be two 1s on it, right next to each other, and you're going to start with the one on the left - I've drawn it up for you here:

Now you can begin. You read the square you're at, and see a 1. Page 1 of the book says that you erase that 1 and leave the square blank, so you do that. You then have to move one square to the right, and keep the book on page 1. Now, our strip looks like this:

We read this new square, and it's also a 1. Just like before, we erase the 1, move one square to the right, and keep the book on the same page. Now the strip is entirely blank:

So, reading the current square, you see a blank. Checking the book, you have to leave it blank, move right one more square and turn to page 2. You read this new square, and it too is blank. You look in the book and ... hang on! This is the last page of the book, and it says to halt! Your job here is done. Congratulations! You have just emulated a Turing machine. Turing machines are a theoretical construct proposed by Alan Turing in 1939 that happen to have two very neat features. The first feature of Turing machines is that they resemble a computer program with an infinite memory capacity - in fact, a programming language is referred to as Turing complete if it can, given such an infinite memory bank, replicate any Turing machine. The second feature of Turing machines is their connection to arithmetic, and particularly the infamous Incompleteness Theorems - which is a topic for another annotation.