Alan Turing (
Turing is well-known for his paper, ‘‘On Computable Numbers, with an
Application to the Entscheidungsproblem (Decision Problem)’’, published
in
Interpreting the solution to this problem as a machine, Turing began to design a computing machine that would be able to resolve all mathematical problems. He discovered that no such universal decision method exists and no formal system could reduce all of mathematics to computational problems. However, in the process of designing his machine, the Turing machine, he summarized the fundamental logistics of what would eventually be the digital computer.
At the outbreak of the second world war, Turing joined an elite team
of mathematician-cryptanalysts. Together, they created a code-breaking
machine named the Bombe, to decipher German messages encoded by their
cipher device, Enigma. From its inception in
A Turing machine is a hypothetical device that very well defined computation and questioned the limits of computation and human thought. It is the simplest form of the computer and the earliest conception of the idea of computers. These machines serve as an ideal computing device and model for mathematical calculation.
That means, that while we can theoretically understand and use the device that Turing designed, it is not possible to replicate in real-life due to the optimal conditions that the device works in. For example, the machine does not consider quantity of information, processing time, and materials.
There are a few parts to the Turing machine. First is a head that acts as a scanner and both reads and writes the data passing through it. The data is stored in the form of an infinitely long paper tape divided into squares with each square bearing a simple symbol. In this lesson, we will consider the symbols ‘0’ and ‘1’ in our explanations and examples.
Inside the head is a second form of working memory called the indicator. At any point in time, the indicator is set to one of a number of ‘positions’, specifying the machine’s present state. For instance, it may track the last symbol that was encountered.
During a computation, the machine performs one of five different operations:
read/identify the symbol on the square under the head
edit the symbol by either i) writing a new one and replacing the first or ii) erasing the current symbol
move the tape one square to the left or right
halt/stop
change state
The computers that we use on a daily basis are designed to perform operations much more complex than the those listed above. Despite its simplicity, the Turing machine can perform the same computations as any modern computer due to its abstract nature. Furthermore, a Turing machine is an ideal device and therefore, not limited by real-world constraints, such as a finite amount of memory.
In this section, we will go over some examples to demonstrate how a Turing machine operates.
The machine in this example will be given an endless blank tape to
start. We want to set up the machine such that, when in motion, it
prints alternating binary digits,
For this to occur, the machine will utilize four states. We will call
them
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 0 | left | ||
blank | left | |||
blank | 1 | left | ||
blank | left |
So, the first cycle of activity from the machine will occur as such.
Recall that the machine is given an infinitely long blank tape.
The bold square represents the square under the head to start. This
could be any square on the tape.
The machine starts in state
Now, the tape is moved to the left while the scanner stays in the
same position so, it will next read the symbol one square to the right.
The machine simultaneously changes to state
The machine is now in state
The machine is in state
Then, the tape moves to the left and the square to the right is
under the scanner. The machine changes to state
With the machine in state
Finally, the machine is once again in state
This machine will continue on endlessly, printing the desired alternate sequence of digits. However, this infinite process does not show the halting capabilities of the machine and is not realistic for everyday purposes.
Let’s take a look at a similar example as the program above. This
time, the machine will simply print the sequence of digits ‘‘
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | 1 | left | ||
blank | 1 | left | ||
blank | 0 | left | stop state |
Then, the program will run as follows.
Recall that the machine is given an infinitely long blank tape.
The bold square represents the square under the head to start. This
could be any square on the tape.
The machine starts in state
The tape is moved to the left while the scanner stays in the same
position so, it will read the symbol in the square to the right. The
machine now changes to state
The machine is now in state
The tape is moved to the left so the square to the right is under
the scanner, and the machine changes to state
The machine is in state
Finally, the tape moves left, the scanner is over the square to
the right. The machine changes to the stop state which halts the machine
and stops running the instructions given.
So far, we have been printing symbols on blank tapes. In this final
example, we are going to be inverting the
State | Scanned Symbol | Move Tape | Next State | |
---|---|---|---|---|
blank | right | |||
right | ||||
right | ||||
blank | stop state | |||
right | ||||
right |
Observe that this time the tape is being moved to the right so, we
are reading the tape from right-to-left. The machine starts in state
The machine is given the tape from the second example. The bold
square represents the square under the head to start.
The machine starts in state
The tape is moved to the right while the scanner stays
in the same position so, it will read the symbol in the square to the
left next. The machine changes to state
The machine in state
The tape is moved to the right so the square to the left is under
the scanner, and the machine stays in state
The machine again reads a
Then, the tape moves to the right so, the square to the left is
under the scanner and the machine returns to state
Finally, the scanner reads a blank while in state