Alan Turing and his Machine
There are two people in a wood, and they run into a bear. The first person gets down on his knees to pray; the second person starts lacing up his boots. The first person asks the second person, “My dear friend, what are you doing? You can’t outrun a bear.” To which the second person responds, “I don’t have to. I only have to outrun you.”

Who was Alan Turing
His full name was Alan Mathison Turing and he was born on June 23, 1912, and died on June 7, 1954.
Alan Turing paved the road for the future development of the theoretical computer science and artificial intelligence. He provided solid concepts of algorithm and computation withe the Turing Machine which can viewed as the prototype of a modern-day computer.
One of his biggest contribution during World War II
During the Second World War, Turing worked of the Government Code and Cypher School at Bletchley Park, Britain’s codebreaking center.
He was a leader of a sector that was responsible for German naval cryptanalysis. He contributed many techniques for speeding the decrypting German ciphers, including improvements to the pre-war Polish Bombe method. Bombe was an electromechanical machine that could find the settings for the Enigma Machine.
What was Enigma Machine? Great question!
The Enigma machine was a series of electro-mechanical rotor cipher that was developed to protect commercial, diplomatic and military communication. It was invented by a German engineer Authur Scherbius at the end of the World War I. The one Alan and his team had to intercept was a version used by Nazi Germany and this particular model had plugboard. This plugboard added more complexity to the code that was produced.
Turing was the main driver when it came to cracking the intercepted code message that helped the Allies to defeat the Nazis in many crucial battles. Including the Battle of the Atlantic, thus assuring the victory.
There a difficulty measuring the effect of Bombe and Turing’s involvement with the length of the war. This is due to the fact that everything was carried out in secret. However, some studies show that Alan’s team shortened the war by two years and saved over fourteen million lives.
Now that you know how great he is, let’s talk about one of his work that is relevant to us.
The Turing Machine
As a human we make our decision by the intuition, but what about computers? The computer runs on a program or on the algorithm. But what is a program or algorithm? and this where Alan Turing answered that question with his notion of a Turing machine.
Turing was working on a problem in Formal logic and as part of his proof he had come up with the notion of any possible algorithm or any possible machine. He had to come up with a very general way of capturing how algorithms or programs or machine would work.
The way Turing describe these machines goes like this:
You have a way of writing down information in a coded form.
He brought up the idea of a tape which is as long as it needs to be.
The tape is divided up into squares and each of the squares contains either one or a zero or space.
Our “machine” looks at the tape one square at a time.
You can think of it as a smaller robot running above the tape and looking one square at a time and that information codes up a question or a problem that we want to solve.
For example, if for instance, you’re in state number 23.
If the number is 0 then erase the zero then put 1. After that is finished, move right to the state 213.
Or if you are in state 213, if the number is 1 then take no action and move left to state 666.
What the machine does, is it starts off with a certain pattern of ones and zero. It follows these rules one square at a time, transforming that string of ones and zeros into a different string of ones and zeros.
If and only if when the program finishes, the machine moves into a halting state. After it finishes we are left with an answer to our initial problem in a binary statement.
If we think about this, this is the foundation of how the modern computer works at a lower level.
And here is the more mathematical statement of what I described above.
A turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or
a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions. A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, B, F) where:
Q is a finite set of states
T is the tape alphabet (symbols which can be written on Tape)
B is blank symbol (every cell is filled with B except input alphabet initially)
∑ is the input alphabet (symbols which are part of input alphabet)
δ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.
q0 is the initial state
F is the set of final states. If any state of F is reached, input string is accepted.
