🎒 History: Stored-program and the Turing Machine

Hey 👋,

I sent the first issue of GIMTEC this September to 10 friends, now I am sending it to 392. It makes me happy to see so many people subscribing and I really hope you all enjoy it as much as I do.

Next week there won't be an issue. Most people are on holiday and for me, one of the worst things about coming back is to see the email inbox full. I don't want to be part of that full inbox.

This article closes some kind of circle at GIMTEC, my first post was also on the Turing Machine, I had just finished reading The Annotated Turing and found Turing's paper fascinating.

This article approaches the topic from a different perspective and adds a little bit more than a description of the machine that Alan Turing introduced in 1936. To put it in perspective, 1936 is 85 years ago, before World War II and TVs.

Understanding the history of how something came to be, helps me understand how it works. Therefore, instead of explaining the concept of a stored-program in computer architecture. I would like to explain how the concept was born.

Initial Computers

A Colossus Mark 2 codebreaking computer being operated by Dorothy Du Boisson (left) and Elsie Booker (right), 1943

The image above is the Colossus, the first programmable, electronic, and digital computer. It was developed in the years 1943-1945 to break encrypted codes.

The Colossus is one of the first “programmable” computers. That means that it could do different tasks. Yet, to reprogram the Colossus, the operators had to rewire and change switches.

The “software developers” of the Colossus were electrical engineers.

Turing Machine

A Turing Machine is an imaginary machine that Alan Turing invented in a paper he published in 1936. This machine can compute numbers mechanically.

How does a Turing machine work?

A Turing Machine can print on a very long tape of cells. It can print characters (a, b, x, etc.) and 0s and 1s.

The machine has a head that is always on top of one cell. Apart from that, these are the machine's functionalities:

• The machine can read the symbol in the cell.
• It can print a symbol in that cell or change it.
• It can move to the left, right, or not move at all.

The machine is playing a game in turns with itself. In each turn, it performs one, some, or all steps mentioned above. For example, it can read the symbol, print a 0, and move right. Or it can just move left. The configurations of the machine define what to do in each step.

Each configuration has:

• A name or identifier; used to refer to it.
• Symbols to be matched.
• A set of operations for each symbol matched.
• The next configuration.

A Simple Turing Machine

It’s always better with examples, so let’s take a look at a machine that prints 0s and 1s alternatively. The configurations for this machine are:

The machine always starts at configuration B —for "begin"—. In our example, the machine starts with a blank tape, but that doesn’t need to be the case, as we’ll see later.

• It starts at configuration B
  • It reads the symbol in the cell: blank
  • It moves to the operations: P0
    • P0: Prints 0
    • R: Moves to the right
  • It sets the following configuration: C

• It starts at configuration C
  • It reads the symbol in the cell: blank
  • It moves to the operations: P1, R
    • P1: Prints 1
    • R: Moves right
  • It sets the following configuration: B

It comes back at configuration B and keeps going like this forever.

This is actually how a Turing Machine operates. The beauty lies in the configuration. Each machine has different configurations; with these configurations, each machine can compute different tasks.

I wrote more about the Turing Machine in my article “Why is the Turing Machine Important” to learn more.

What is different in the Universal Turing Machine (UTM)?

If a modern computer is a Universal Turing Machine; the old iPod is a simple Turing Machine, a machine that only plays music.

The iPod can only do some specific tasks, yet the modern computer can do many different tasks.

As we learned before, the Turing Machine has configurations. The UTM is a special case of the Turing Machine; the configurations of the UTM are what make it special. It has such a set of configurations that it can do more than one task. The same way a computer can do more tasks than an iPod.

How can the UTM perform different tasks?

The key is in the tape; the UTM uses the tape to read and perform a different action depending on the value it has read.

Instead of an empty tape, the machine starts with some values. The machine reads the values and then performs different operations.

This is the same way that our computers work. The computers read the instructions from the RAM; the instruction tells them what to do.

This is how we create a machine that can do many different tasks: storing the tasks in memory.

Storing tasks (or instructions) in memory is the “Store Program” concept.

Both the UTM and modern computers read instructions and perform different tasks depending on what they read. Instead of having fixed functionality, their main feature is reading and performing depending on what they read.

It’s like teaching someone to read instructions instead of telling them what to do.

The UTM achieves this with a special configuration that follows the same rules as simple Turing Machines: scan a cell, print symbols or numbers, move and change the configuration.

Modern Computers are electrical circuits that can read electrical currents and perform different calculations. This electrical circuit that can read and perform calculations is equivalent to the configurations of the UTM.

The configurations of the UTM are like the hardware architecture of modern computers.

Universal Turing Machine vs. Modern Computers

A table of similarities between the Universal Turing Machine and modern computers.

One of the biggest contributions of the Universal Turing Machine is the idea of reading the instructions from somewhere instead of having the functionality hardcoded in the machine. This idea is the stored-program concept.

If you like this post, consider sharing it with your friends on twitter or forwarding this email to them 🙈

Don't hesitate to reach out to me if you have any questions or see an error. I highly appreciate it.

And thanks to Michal for reviewing this article 🙏