The video that I want to do today is a direct follow-up of the one I did a few
weeks ago whichh Sean so what misguidedly entitled "The Most Difficult Program to
Compute?". It was, of course, all about the Ackermann function. Today I
want to show to you the Busy Beaver problem - or the Busy Beaver game, and it
is far worse than Ackerman [in its behaviour]. It was invented by a gentleman called Tibor
Rado, in 1962. What he, in his later years, took on, was to teach beginners about
Turing machines. Now many of you on the Sean and Brady wish list of topics to be
covered said: "I want to know about Turing Machines - I want to know about
Undecidability". So, this is a lovely way to pull it all in because this thing,
this program, that behaves even worse than Ackermann, depends, and is utterly
related to, the idea of a Turing machine. For those of you want just a bit more
detail about what's going on at the Turing Machine level and exactly how
Tibor Rado developed a particular form of Turing machine suitable for this game,
then I'm going to refer you to this short introductory movie [Computerphile: Turing Machine Primer] So, let's look
at the particular formulation of a Turing Machine that Tibor Rado
formulated as a game, which you can play with your computer program and in fact
there's Web pages devoted to this. You can join in on the Busy Beaver community and
see if you can find a Beaver that's even busier than the ones currently known.
But be warned. As you want to go up and up and up in size of this problem it [the computation load] goes
up worse than super exponentially! This is the single state Turing machine for
the [easiest] Busy Beaver problem. What the heck is this Busy Beaver problem? Busy Beaver
asks what is the maximum number of 1s that get printed on your tape, for your
given Turing Machine, when it halts? Now, I've got to add that
to the end because, as you'll discover, there are some - there are lots! - of rogue
Turing Machines which will go berserk, either printing endless 1s or even
overwriting them with endless 0s, and going either to the right, or to the left.
So - these well-behaved ones - we want them to halt and stop and just leave
a big, big tape with lots of 1s and 0s on it. And it's called Busy Beaver because
this program is just going bananas, walking up and down the tape, writing
1s and 0s, seemingly arbitrarily, but in accordance with the program
instructions on the cards. And you're just saying: "How many 1s do I end up
with?". What's the best or worst I can do? Well, I think this will become a bit more
alive to you, now, if we take a real, actual example of a single-card Turing
Machine for Busy Beaver. So we stick our read/write head in the middle of this
tape to start off with. There it is. And this is card 1. It is the only card
available to us because this is a one-card Turing Machine. [The] rule is, your start
card is always card 1. The first thing you say is: "read a symbol". So you
read a zero. OK? What does the instruction card tell me to do? It says:
"overwrite it with a 1" Here's the overwritten 1. 0, remember, means "move to the left" that
makes 0. So you move the head to here: 1. That means "go back to instruction card 1".
I'm already in instruction 1, so what I do is go back in there, like that, but now,
again, you say: "Read what's under the head". - well the heads moved to here - but you're
under another 0 now. So you say OK, overwrite that 0 with a 1, shift to the
left because that's what the 0 means. Oh blimey! move the head here. Go
back to state 1 - [but] we're already in state 1, go back and do it again. You can see,
straight away what's going to happen here: I'm going to whizz off to the left
writing 1s and it will never, never stop. So here's the first example then
of what I referred to in the previous video. I told you there were things
called recursively enumerable programs that sometimes stop and sometimes just
whizzed into loops and went on for ever. Well, it's a nice simple example of it
given that, right at the start, you probably don't know whether your given
program is going to whizz left or right, or whether it's just going to mess
about in the middle. Start it in the middle. Give it enough space to go left
enough space to go right. But the rules say, in principle, if it needs
infinite tape give it enough. Now a lot of the art of this kind of programming
is to say: "Ah! but is it looping"? It's pointless giving it infinite tape if
it's just going to loop and loop and loop, and not do any different thing,
forever. And yeah, very very clearly this one's looping. So, we've done a one-card
Turing Machine, Busy Beaver attempt, here and [have] just seen how easy it is to get into
a loop and spin off doing zillions of 1s that will never end. And you might
say: "Oh! that's the idea then is it? A sort of infinite Busy Beaver: it just spews
out 1s for ever?" And, unfortunately, the rules of the games they
say: "No, that doesn't count it's got to halt!" There's got to be a finite number of
1s that you can count. 1s that just go on forever don't count. So, you need to
get into a 'halt' state, somehow or another, and have a finite number of 1s to
count up. So, let's do one that is still a single-card candidate for a Busy Beaver
Turing Machine, but one that doesn't loop indefinitely. This time I'm going to make
it be 0 - if I read a zero then my actions are 1 1 0. Actually some of you
will have spotted already that in a one-card set up like this, given that you
move the head off to the left or the right, all you ever encounter is zeros,
you are not going to get into a stage of ever reading a 1 because you've
only got one instruction. And you either keep re-obeying it, as we saw last time
when you loop back into itself, or it's a one-off thing and it does one thing and
stops. And in this particular case, well, I'll put 1 1 0 here
for the 1 case. We won't need that because - look what happens - if I've read a
0, which I have there, what do I then do? The answer is I overwrite it with a
1; the next 1 to the right of that, in the instruction layout, says shift right.
Remember a 0 at that position is shift left; this 1 is shift right. So I
shift the read/write head to the right. but then C0 is the Halt state. Wow! Bound
to win an award! It reads a zero it over-writes it with a 1; it shifts one
place to the right and then stops. Wonderful extremes isn't it? It either
whizzes off and never stops writing 1s or else it does precisely one 1 and
then stops, and says 'done it'! Let's just do a bit of mental arithmetic here, it's
not too difficult, in this case. You've got 0 or a 1 as the things you might be
reading, but here you've got a triple of binary digits: it's either 0 or !
that you read; it's either 0 or 1 that you shift - left or right. And it's
either the Halt state or back into 1, which is where you go. Right? So, Sean your
starter for ten: two to the power 3 is 8. You've got that in the zero case, and in
general you've also got to say: "Well, I've got 8 possibilities for the 1 case". So
8 times 8 is 64. There are 64 one card [Busy Beaver] Turing Machines but there's only about 4
possible behaviours; you either zoom off to the left, printing and overwriting the cells
with either 1s or 0s. Or you can write a 1; shift to the left and stop;
1, shift to the right and stop or overwrite a 0 with a 0, shift to
the left and stop, or shift to the right and stop. Not exactly thrilling! But since
the aim of the Busy Beaver game is how many 1s
can you write, regardless of which of the 64 cards you choose - and you must try them
all out - the answer is you never get better than one. You write one 1. Rado
in his paper, calls this e score Sigma (Greek Sigma). The score for a one-card busy
beaver the best you can do is 1. Remember these Turing Machines are just
made up of sets of cards, in order. that's all.
So, for the order 2 - you're going to have a c1 and a c2. If you're having a c2
possibility - a two-card thing - then that final column could be 0 to Halt it;
1 to go back into yourself or 2 to go to the other card.
So, you've got three possibilities in that final column now. So, it's not like 2
times 2 times 2. It's 2 times 2 times 3 Anyway, you work it all out for the two-
card case, would you believe there are 20,736 Turing Machines ... >> Sean: How many? >> DFB: 20,736
This number - which is just: "How many Turing Machines have you got to look at"?
to see which behaves the best in printing out lots of 1s. This only goes
up exponentially - this number - this isn't bad. But each one of those machines can
behave worse than super-exponentially. So Rado's number for how many Turing machines -
you can seat in his paper. I'll leave you to work out for yourself why this is
true the number of Turing Machines, let's call it N(n) n is [4 x (n + 1)] ^ 2n
Let's see if that works. Iif I put in 1 here for n
Right? 1 plus 1 is 2. Two 4s are 8. 8 to the power of 2 x 1. 2 x 1 is 2. 8 squared is 64.
Right? What about if I put in n is 2. 2 plus 1 is 3. 3 x 4 is 12. 12 to the
power of 4, 12 to the power of 4 is 20,736
So your first job is to enumerate all those Turing Machines just get all those
possible two-card combinations that make 20,736 different possibilities and
you can start to weed out the rubbish straight away. You can clearly say, first
of all, if your chosen machine doesn't have a Halt state somewhere in it then
it's never ever going to stop and it can't be a contender.
So you can rule out all the ones that don't have a zero somewhere in a
right-hand column. You can soon get rid of those - cut it down a little bit.
But then you have to start running the Turing Machines to see - like I've done
here - do they halt? If they halt, how many 1s have they written by the time
they've halted? It tends to be the case that all the 1s that get written
are pretty well bunched together, but the rules of the game say that's not
absolutely essential - just start at the far left with the earliest 1, read
across to the right and count up the number of ones you've got. And that's your
score. But it must halt. It mustn't be in part of a "I'm going on for ever", sort of loop.
There are some candidates for best Busy Beaver of the two-card Turing
Machines what's the maximum number of ones that they can print out? 4.
Not very good. What's all the fuss about? When you get on to three-card
Turing Machines, how many of these are there on your shortlist? 16,777,216
three-card Turing Machines. What's the best score you can get off a three card
machine? Still only 6. Doesn't look very ominous or dreadful at this stage.
Four-card ones? How many of those are there? Now I've gone up to about four-card ones
in the program I'll give you. The answer. It's 25.6 trillion
possible Turing Machines, all of which have to be run and their behaviour
investigated. or they have to be eliminate. These are four-card machines.
What's the best score you can get off those thirteen - and this goes worse than
Ackermann - yeah this is the false dawn. It just goes berserk now. When you come on
to five-card Busy Beavers which is where this huge research still going on, the
best score, so far, for a five-card Turing Machine I have not worked out how many
of those are are it's going to be huge, all of which have to be investigated. The
best score, for a five card so far, is 4098.
It's coming up to 25 years ago that that number was discovered.
4098 is the best yet, So, I hear you say, what are they messing about at? They've had 25 years
and all right there's a few trillion, quadrillion?, Turing Machines to be
investigated but all the obvious rubbish would have been weeded out by now? I may
say that the German researchers who discovered this number did have access
to a supercomputer - it does help! What's gone wrong? Why isn't there a
better result and if you look on the Wikipedia page for this you'll find the
answer. The answer is that there are 40 candidates, still running, which might
produce an even better answer than 4098. And you say: "But surely the darn things
are either discernibly looping or else they've stopped"? No - it's really horrible.
This is the nasty part of it you can get Turing Machines where you can't tell
whether they're looping or not. They consume a lot of tape and then they come
back and they overwrite bits of the tape and y' know ... And you think: "Have I seen
that pattern before?" In the case that I did for the 1-state Turing Machine we're
just going: 1 1 1 1 1 1 over and over. It takes no genius to say "Iit's looping and it's
doing nothing but reproducing 1s". But you can imagine that as the numbers go up
you could get very, very long cyclic periodicity, with a periodicity of 20
million (say) or something like this. Tibor Rado and his student were the people who
worked out that for a four-card machine 13 was the best result you could get. But
in getting that result they still had to look at a handful of rogue machines where they
weren't sure whether they stopped or not. Some of them they could prove
programmatically were definitely looping. Others they could use human inference to
argue: "Yes, that is looping, I can show you why?"
So, yeah, 13 is definitely correct [for the 4-card case] But for the five-card case, who knows?
Join the Busy Beaver club. Get your own supercomputer! Do the work!
And somebody out there has gone on to order six. And it is reckoned that the
minimum possible score for an order six Busy Beaver will be of the order 10 ^ 10,500
Now that's getting very close in size to
ackermann(4, 2). Y'know it to two to the sixty-something thousand. Nobody knows what the
right score is. So can you see that's already, by order five or six, you're
getting into Ackermann-size numbers. And one of the things shown on the Wikipedia
page, which will delight you, is that for all sufficient n - and this n is not very big -
Busy Beaver numbers will always outrank Ackermann numbers. And the reason for that
is that, again in the literature which you can look up for yourself, the reason
is that the Busy Beaver can be shown to grow faster than any computable function.
It doesn't matter what you put in there but, if it's a computable function that
has an answer, Busy Beaver can be shown to grow faster than that in the long run.
It may not do so for small n, but eventually it'll overtake it and go
completely mad. So, yes, the answer to the horrible question is: "Are you telling me
this thing gives you even bigger numbers than Ackermann does? Yes, it does. Yes it gets
effortlessly bigger. Some people say; " I don't believe all the
stuff about 'recursively enumerable' - sometimes it can, y' know, sometimes this
machine can stop and give you an answer and sometimes it just whizzes around
forever. Well here you've got it in front of you. And it really is not
terrifically useful. Except it's here as a teaching example of saying "It may seem
pointless but this is the worst can happen with a computer program". You set,
on the face of it, what seems to be a perfectly straightforward thing: "Run this
Turing Machine, hope it halts and then tell me how many 1s it prints out.
But behind that is a huge amount of illustration of theory. You think:
that's going to be no worse than super exponential even when it explodes and
takes off". But this one rockets up far faster than Ackermann and very often you will
say: "If problems are badly behaved they are either super-exponential or they may
be even worse - they may actually be undecidable". And this is what you are
saying in this thing here ...