In the last lesson, we began to define what computation is
with a goal of eventually being precise about what it can and cannot do.
We said that the input to any computation can be expressed as a string
and may assume that whatever the instructions that were for
turning input into output, that these two could be expressed as a string.
Using a counting argument,
we were able to show that there were some functions that were not computable.
In this lesson we're going to look at how input gets turned into
output more closely.
Specifically, we're going to study the Turing machine and
the classical model of computation.
As we'll see in a later lesson, Turing machines can do everything that we
consider as computation and because of their simplicity
they are a terrific tool for studying computation and its limitations.
Massively parallel machines, quantum computers,
they can't doing anything a that a Turing machine can't do.
Turing machines were never intended to be practical but
nevertheless several have been built for illustrative purposes.
Including this one, from Mike Davey.
The input to the machine is a tape, unto which the string input has been written.
Using a read right head,
the machine turns input into output, through a series of steps.
At each step, a decision is made about whether and
what to write to the tape, and whether to move it to the right or to the left.
This decision is based on exactly two things.
The current symbol under the read write head and
something called the machine state.
Which also gets updated as the symbol is written.
That's it. The machine stops when is reaches one of
two halting states, named accept and reject.
Usually we're interested in which of these two states the machine halts in.
Though when we want to compute functions from strings to strings,
then we pay attention to the tape contents instead.
It's a very interesting historical note that in Alan Turing's 1936 paper,
in which he first proposed this model, the inspiration does not seem to come
from any thought of an electromechanical device, but
rather from the experience of doing computations on paper.
In section 9 he starts from the idea of a person who he calls the computer,
working with pen and paper, and
then argues that his proposed machine can do what this person does.
So here I am, a computer, with my pen and paper.
And we'll follow Turing's argument that his machine can do what I can.
Let's take an example.
He's talking about computable numbers, so I'll compute a very simple number,
Alan Turing's age when he wrote the paper.
So we'll take 1936- 1912, which is equal to 24.
He argues that any calculation like this can be done on a grid.
Like a child's arithmetic book her says.
I assume he means something like wide ruled graph paper.
He argues that all the symbols can be made to fit inside one of these squares.
Then he argues that the fact that the grid is two dimensional
is just a convenience.
So he takes away the paper and says that computation can be done on a tape.
As someone who has to carry out the computation, I don't much care for this.
But I can still do my job.
Then he points out that there are limits to the width of my perception.
So if I happen to be reading a very long mathematical paper,
the phrase "hence (applying this big Theorem number) we have.
Then when I look back,
I probably wouldn't be sure at a glance that I had found the right theorem.
I would have to check, maybe three or four digits at a time,
crossing off the ones I had matched, so as not to lose my place.
Something like this.
So I match the first four, then the next four, and so on.
And so forth.
Eventually, I will have matched them all and can re-read the theorem.
Now, since Alan Turing was going for the simplest machine possible,
he takes this idea to extreme and only let's me read one symbol at a time and
only move right or left one square on the tape at a time trusting
to the strategy of making marks on the tape like I did with this theorem here,
and my state mind to accomplish the same things as I would
under normal operation with pen and paper.
And with those rules, I have become a Turing machine.
So that's the inspiration, not a futuristic vision of the digital age,
but probably Alan Turing's own everyday experience of computing
with pen and paper.