Introduction to Turing Machines
Get an introduction to Turing machines and their relationship to PDAs and post machines.
We'll cover the following...
Historical background
In this lesson, we'll study a type of machine called the Turing machine (TM), named after the mathematician Alan Turing, who proposed the idea in 1936. At the time, he was trying to show that no universal algorithm could decide all logical mathematical questions, as the celebrated mathematician David Hilbert had proposed. It naturally followed that Turing needed to precisely define what an algorithm is. Others were also working on solving the same problem (notably Kurt Gödel, Alonzo Church, and Stephen Kleene), but it was Turing’s formulation of the nature of computations that proved to be the simplest and most effective, and also provided a sound theoretical foundation for the computer revolution.
His abstract “machines” prefigured what we now understand as a low-level computer instruction set. More importantly, it was Turing who introduced the notion of a program as input and simulating their behavior (i.e., “executing” them), which strongly influenced the development of the digital computer. But before we look at Turing machines, let’s consider what we can do with a pushdown automaton with two stacks.
PDA with two stacks and Turing machine
We know that the language is not context-free, but a pushdown automaton with two stacks can recognize it. We use one stack to match the ’s and ’s, and the other to match the 's and ’s. See the 2-stack PDA below.
There are two entries for stack operations—one for each stack. The pattern for each transition is <symbol>, <pop1><push1>, <pop2><push2>. The following table traces the string through the 2-stack PDA.
| State | Input | Stack 1 | Stack 2 |
|---|---|---|---|