Pioneers - Alan Turing
Theories and Influence of Alan Turing
Key Concepts |
| A Theoretical General Purpose Computer | While the technology did not exist to build his vision, Turing, nevertheless, defined the components and interactions needed to create a general purpose computer |
| Maintaining State | The state machine is the heart of Turing's theory, allowing a computer to operate based on changing inputs and internal events (state changes) |
| The Turing Machine | The theoretical model that defined the actual creation a decade later |
Introduction
Alan Turing (1912 - 1954) was an English mathematician, cryptographer, and creator of theoretic computer science. His legacy as a scientist, philosopher, and world war 2 code breaker lives on in scientific and popular culture.
Life of Alan Turing
Alan Turing - Wikipedia - June 23, 1912 - June 7, 1954
Among his many contributions to computer science, he imagined a machine that could run any program, solve any problem, and, without the technology to build one, designed the first draft of the modern computer architecture.
Turing Machines Explained - Computerphile
Turing Machines are the basis of modern computing, but what actually is a Turing Machine?
Assistant Professor Mark Jago. Copyright CC BY International
A Theoretical General Purpose Computer
While not a new idea, the first general purpose digital computers were decades away in the 1930's when Turing described his simple stored-program computer. Turing would describe the elements needed and the mechanism to maintain information (states) during program execution.
The Turing Machine
In 1936, Turing revealed his theoretical automatic machine or a-machine. It would later be called the Turing Machine
Without the technology to build a prototype, Turing defines components that we recognize today as a modern computer
By Rocky Acosta - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=24369879
Tape
The Tape is an infinitely long read/write ledger of data. It is made up of cells, each containing a single symbol that the machine understands.
We'd recognize the Tape in today's computers as data stored in RAM/External storage.
Head
The Head can read/write symbols to/from the tape. It can move the tape as ordered by the Instructions.
State Register
As the Turing machine runs, it maintains a current state, based on reading from the tape. The state drives the next instruction to execute. The State Register holds the current state for reference.
While the State Register is a simple storage device, it functions as the modern Controller. It drives what happens each instruction cycle
Instructions
Each instruction can both react to previous events and act to modify the machine for future instructions. When executed, an instruction first reads the State Register. Next it reads the data at the current head position. With these two (2) pieces of information, the instruction may cause in one (1) or more of the following actions:
- State change
- Update to data on the tape at the current head position
- Movement of the head one (1) position left or right
Together a set of Instructions make up the program that runs on a Turing Machine. It is equitant to modern computer programs, although considerably simpler.
Instructions makes Turing Machines General-Purpose computer.
A program in a simple Turing Machine contains rows of states. Based on the current state, the correct row is executed and the state is updated for the next instruction cycle.
Sample Turing Program
The Turing Machine instruction system is as follows:
- Read symbol from current head position
- Use State Register S0 and newly read symbol to select program row to execute
- Following selected program row:
- Write symbol (Wt) to tape
- Move Head Mv direction
- Set State Register to S1
| S0 | Rd | Wt | Mv | S1 | Description |
|---|---|---|---|---|---|
| A | - | - | Lt | B | If in state A -and- blank is read from the Tape: 1) Write blank to the tape, 2) Move Head to the Left 1 space, and 3) Switch to B State |
| A | 0 | - | Rt | A | If in state A -and- 0 is read from the Tape: 1) Write blank to the tape, 2) Move Head to the Right 1 space, and 3) Stay in A State |
| A | 1 | - | Rt | A | If in state A -and- 1 is read from the Tape: 1) Write blank to the tape, 2) Move Head to the Right 1 space, and 3) Stay in A State |
| B | - | 1 | Rt | C | If in state B -and- blank is read: Write 1, Move Right, Switch to C State |
| B | 0 | 1 | Lf | C | If in state B -and- 0 is read: Write 1, Move Left, Switch to C State |
| B | 1 | 0 | Lf | B | If in state B -and- 1 is read: Write 0, Move Left, Switch to C State |
| C | - | - | Lf | HALT | If in state C -and- blank is read: Write blank, Move Left, HALT |
| C | 0 | - | Rt | C | If in state C -and- 0 is read: Write blank, Move Right, Stay in C State |
| C | 1 | - | Rt | B | If in state C -and- 1 is read: Write blank, Move Right, Stay in C State |
Animated Turing Machine
Below is an animation of a simple Turing Machine.
This example has 3 states (A, B, and C) and 2 symbols (0, and 1).
The purple bar shows the instruction being executed.
Source: https://www.futurelearn.com/info/courses/how-computers-work/0/steps/49259
Turing Machine Simulator
Check out this simple simulator by Anthony Morphett Morphett.info Turing Machine Simulator
- Select Load and Example Program and select Binary Addition
- In the Initial Input field, enter 100 1110 (4 and 14 in base 10, note the space between the two values)
- Click Reset
- Click Run
- The machine will execute the programs and the Tape should display 10010 (18 in base 10)
Repeat the steps, but use the Step button to see each Instruction Cycle of the Turing Machine
Conclusion
Turing defined a theoretical general purpose computer with the basic components used in today's actual computers.
Using a State Machine made the design general. Changing the state machine (effectively a program) made the Turing Machine a general purpose system.
Use of a Tape to supply data into the computer and update data as the program ran was a key to simple design.