How Alan Turing’s simple thoughts disrupted an entire industry (Day 2)

What is a Turing machine? How it works? #

Statue of Alan Turing, Bletchley Park - Photo by Bletchley Park on flickr

Hi, today we will be talking about one of the pioneers of modern computers (in the previous article, when we talked about quantum computers, I have called the same a classical computer) and his contributions. He, Alan Turing in 1936 proposed a hypothetical machine, which we call a Turing machine (TM), is considered as the base design of the computers that we use today. Despite its simplicity, the machine can simulate any computer program.

Photo by cam.ac.uk

The above image represents a simple TM. Just like our computers have memory or internal storage, this machine has got an infinitely-long tape. The tape is divided into different blocks. Three operations can be performed on these blocks with a head attached to it.

• we can move our tape to the either left or right, one block at a time (move operation)

• read a value from the block currently under the head (read operation)

• replace a value in the block currently under the head (write operation) Suppose we want to write a binary sequence 110 to this tape, what should we do? We will perform a write(1), move(left), write(1), move(left), write(0) to write the sequence 110 to tape. Simple design, right?

Programming a Turing machine #

I can walk you through a simple example (the examples in this and the upcoming article are taken from cam.ac.uk computer lab page) on how to program a TM. In the above example, we already have written a binary sequence 110 to our machine's tape and the machine head is staying over 0. What we're going to do now is, instruct our machine to flip each of those binary characters (0 will become 1 and vice versa). Let's write our logic in a table form to make an intuition.

When the machine head reads a blank block, it should do nothing. If it reads a 0 from that block, the head should write back a 1 and move the tape to the right. If the head read a 1 it should write back a 0 and move the tape to the right. So the action sequence will be read(0), write(1), move(right), read(1), write(0), move(right), read(1), write(0), move(right), read(blank), read(blank), read(blank), ...

Finally, we need to give those instructions in some format, that our machine will understand (this process is known as programming). As you can see, the main drawback in the above logic is, the process will be repeated forever doing read(blank). How to solve that issue? Yes, it can be solved if we could control the states of a machine, including the terminated state. So, let's add states managements to our logic.

The machine will start in state 0 and will follow the instructions within that state until a state transition occurs. Once it moves into another state, everything else is left behind and will follow instructions valid for that new state. When it reaches the stop state, the process will be terminated.

Wow, congrats. You are ready to program your hypothetical turning machine! Can we keep that excitement until next article? I'm going to build a toy Turing machine for you to play by coding what we've learned. Until then