I've just done a film about a special class of Turing Machine called "Busy Beaver"
that enables you to play the Busy Beaver game. So there's lots of wonderful
video footage you can see, on that.
However for those of you new to this game, who aren't familiar
at all with how Turing Machines work, what we've now done
is sectioned off a little piece of footage that you could watch,
first of all, to get some idea of
Rado's - Tibor Rado who invented the Busy Beaver game -
how he designed his particular Turing Machine
to enable this game to be played.
First of all, what does a Turing Machine actually look like - what does it do?
So here we are then. This is a Turing Machine tape, it's divided up into lots
lots of notional cells
these are memory locations. Into these memory locations you can put
patterns of bits that represent
your program; patterns of bits that represent the data you're working on, in the
data part of memory,
and you can have an infinite amount of it, in principle. The
only other thing you need to give you this universal computing model
is a read / write head. It visits a location on the tape
and you can either issue to it a "read" command or a "write" command. Now suppose
these cells have been pre-initialized with zeros. If in the current head position you say
"read" and tell me what it is it says it's a zero. You can then,
if you want to, say "I want to over-write that with a one"
So, in every cell of this memory there
is the ability to erase and optionally to overwrite
with something else. Now, you can if you're completely masochistic - and some Turing
Machine programs work out like this - you could always over-write a 0 with a 0,
it's not going to stop you doing that. So, it can shift
left, or right, or not at all.
And this is a binary Turing Machine.
There are other formulations which try to make life simpler
and keep the tape shorter, by saying: "Oh! I'll let you work in decimal
arithmetic". What was discovered very early on was that it really didn't matter
how fancy your alphabet was for the tape.
All Turing Machines were the same -they all had the same computing power,
It's just that sometimes you can keep the tape length shorter.
OK, so where does the program come from
that causes this head to read, and to write and to shift.
In many Turing Machine primers
your say: "Let's park the program code
- as tons of ones and zeroes, at this end of the tape
and data in memory
at the top end the tape. And you'll read an instruction,
it will tell you something to do with the read/write head and you shift the head up
into the data section. You'll do it and you're oscillating back between
reading program and writing data. The simplification I'm going to do
which is what Tibor Rado does on his Busy Beaver Turing Machine, and it makes life
so much simpler,
but I'm gonna take the program code off from tape
- sounds like good old fashioned computing - onto cards.
Not punched card of the sort we've covered
but a Tibor Rado card. Here's a typical
Tibor Rado type Turing Machine
card and the idea is that every card represents an instruction
in a Turing Machine. So let us look at this card
in the context of this Turing Machine tape here.
Tibor says, for the sake of argument, let's assume that all these
data memory cells are initialized to zeros.
Since you don't know whether the head is going to shift to the right a lot, or
shift to the left a lot ahead of time,
let's put it in the middle of this tape here, Zero here means
if you've got a 0 under the head at the moment - in other words you read and you see a 0 -
it then says here the '1' is the
character to be written. So
we have read a 0, it now says "Write a 1"
Second binary digit here says
"Now move the head" and again what Rado did
is not absolutely essential in Turing Machine law, but he said
"If I make the Turing Machine work like this it's a lot easier to show you what's
going on".
So please forgive me in the Rado Machine the head must always move.
You can't say " No, I'm stopping still here" You either move left or you move right.
Zero equals left; one equals right.
And finally what's this '2' here?
Thats your next instruction: '2'.
We're on card '1' - your next instruction will be on another card - card '2'.
So, you've got all of these actions, that must happen
if you read a zero in this current state of the machine.
C1 is the Start card,
C0 is the Halt card.
OK, so if something in one of these instructions says you're next card is 0
meaning a Halt - the 0 card is the Halt card. So that's the general
layout of these cards. Well now having seen this introduction I'd encourage you
to go on and watch the main "Busy Beaver" movie.
And I think at the end of that you'll get some real feeling
for just what the word 'Undecidability'
actually means.