History: Stored-program and the Turing Machine
5 min read

History: Stored-program and the Turing Machine

Understanding the history of how something came to be, helps understanding how it works.
History: Stored-program and the Turing Machine

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

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:

Identifier Symbol Operations Next Configuration
B None P0, R C
C None P1, R B

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.

Universal Turing Machine Modern Computer
Read instructions from a tape Read instructions from memory (RAM)
Can perform many different tasks with the same configuration Can perform many different tasks with the same electrical circuit
Stored-program computer Stored-program computer
The task to perform can be changed without changing the configuration The task to perform can be changed without changing the electrical circuit: This software development

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 🙏

Thanks for reading, don't be a stranger 👋

GIMTEC is the newsletter I wish I had earlier in my software engineering career.

Every other Wednesday, I share an article on a topic that you won't learn at work.

Join more than 3,000 subscribers below.

Thanks for subscribing! A confirmation email has been sent.

Check the SPAM folder if you don't receive it shortly.

Sorry, there was an error 🤫.

Try again and contact me at llorenc[at]gimtec.io if it doesn't work. Thanks!