What are the essential features or primary functions of a computer (in whatever sense that word means to you)?
What is computation or the main features of computation?
Do you think the idea of computer can be separated from the physical, engineered devices we use in everyday life?
What happens when you interact with a computer?
Going back to the Entscheidungsproblem, Hilbert requested an “effective procedure” for deciding the validity of mathematical statements (a very limited realization of a dream of Leibniz).
Addressing Hilbert’s problem requires one to make precise what is an effective procedure (algorithm).
Once we are all on the same page regarding what an effective procedure is, we can ask “what can such a procedure do”?
Church, Gödel, Post, Turing, and others formulated definitions of an effective procedure that provided models for computation.
Turing’s approach, while logically equivalent to the others, was simple and influenced the engineering of the modern computer.
Multiply 123 by 45 by hand.
Describe the mental processes that occurred when you carried out the multiplication.
Let’s explore some simple Turing machines. 1
Once you’ve constructed some simple Turing machines, it’s easy to grok how one might construct Turing machines to accomplish all manner of tasks of an algorithmic nature 2.
For the sake of culture, let’s examine some of the formalities of Turing machines.
A Turing machine \(M\) includes a two-way infinite tape divided into cells, a reading head which scans one cell of the tape at a time, and a finite set of internal states \(Q = \{q_{0},q_{1},\ldots , q_{n}\}\), \(n\geq 1\). Each cell is either blank (B) or has written on it a symbol from a set \(S\). In a single step the machine may simultaneously:
The operation of \(M\) is controlled by a partial map \(\delta: Q \times S \rightarrow Q \times S \times \{R,L\}\). 1
A function is effectively calculable by a human being if and only if it can be computed by a Turing machine. 1
If we can prove that some particular task cannot be accomplished by a Turing machine, we can conclude that no algorithmic (effective) procedure can accomplish that task.
Turing did exactly that and thus provided a negative answer to the Entscheidungsproblem.
Returning to our Turing machine examples, we see that some machines halt while others do not.
Turing applied a technical tool to this situation to construct problems that cannot be solved by Turing machines.
The technical tool used by Turing is known as Cantor’s diagonal method.
We will explain this method and use it to demonstrate that one of the sets \(\mathbb{N}\), \(\mathbb{Q}\), and \(\mathbb{R}\) is not like the other two in a very fundamental sense.
Turing essentially did the following:
Following a technique of Gödel, he assigned natural numbers to sets of quintuples corresponding to Turing machines.
He applied Cantor’s diagonal method to construct a particular set \(D\) of code numbers of Turing machines.
He showed that no Turing machine can solve the problem: Find an algorithm to determine for a given number whether or not it belongs to \(D\).
That is how Turing addressed the Entscheidungsproblem.
Turing did another very interesting thing in his paper on the Entscheidungsproblem.
In addition to resolving the Entscheidungsproblem, Turing showed how to construct a Turing machine that could do anything that could be done by any other Turing machine. That is, a universal Turing machine.
Thus, Turing provided a mathematical model of an all-purpose computer.
The notion of Turing machine arises from an analysis of what humans do when computing.
This led Turing to ponder “thinking machines.”
From there, Turing considered ways to test a machine for intelligence and developed the imitation game or Turing test.
Chapter 2 Algorithms: From Al-Khwarizmi to Turing and Beyond from Turing’s Revolution edited by Sommaruga and Strahm
The Emperor’s New Mind by Roger Penrose
The Universal Computer: The Road from Leibniz to Turing by Martin Davis
Turing Computability by Robert I. Soare
Computability Theory by Rebecca Weber
The Honors Class: Hilbert’s Problems and Their Solvers by Ben Yandell