So far we've looked at primitive recursion
- things where you can use recursion if you want to, but you don't have to
because it can be de-recursed and turned into an iterative "for" loop.
We did factorial and we did fibonacci
both of which are primitive recursive in this sense.
And there'll be a great danger in thinking well, surely,
you can do anything then in "for" loops, why bother with recursion at all?
Well, there are some things which are so fundamentally recursive
that you just have to do them recursively.
It became clear to mathematicians really at the turn of the last century
about the nature of functions in general that
there were some things that were so - if you like - huge, so enormous, so badly behaved
that they just had to be recursively defined.
And I think one the earliest people to realize this was
a research student of David Hilbert's -- now
who is David Hilbert? We're back on Numberphile territory again !
Probably, perhaps, the greatest mathematician of the late 19th and early
20th century.
He was a phenomenal mathematical
genius, capabilities, and so on
He was at Goettingen, in Germany, and I think I'm right in saying that
Ackermann was one of his research students and it's Wilhelm
Ackermann's function that we're going to look at today.
The test was, can you come up with something that just has to be done
totally recursively - you can't do it, as it were, in a "for" loop
even though those hadn't been properly invented at that stage.
What became clear as a result of
work started by Ackermann, and by others,
is that we've got a hierarchy of program types:
Right down at the bottom - the simple ones we've seen -- the ones that can be de-recursed,
these are Primitive Recursive. There's a whole layer on top of that
where they're functions where you just have to define them
recursively. Just above this set are the
Recursively Enumerable functions
Let's be clear here, by saying Primitive Recursive at the bottom
I'm including every other program that isn't recursive
I'm regarding a thing that just goes through a sequence as being a very
simple example of
a primitive recursive program with no real recursion in it
and anything that's got "for" loops or nested "for" loops, well actually
you could have done that recursively, and probably languages like Haskell do
for all I know.
But they still count as the simplest form of program
- primitive recursion if it's got recursion in there at all
you could always de-recurse it - make it into "for" loops, This next thing
Recursive, on top of that, there's an even more problematical set of programs,
above that, which says they're recursive,
but for some values of the arguments you put into the function
they will stop and give an answer and for others
they will go on for ever and they will never ever stop.
[How do you define 'for ever' then, go on]
Forever and ever and ever - they will go into just repeating the same old stack
frames and you may not be aware of it
and just go round and round. And then you'll say: "But how can I decide ahead of time
for given arguments, whether it will stop or won't ?"
And the answer is - Hello Alan Turing -
in general that may well be Undecidable.
So above here, out in hyperspace, is the Great
Undecidable Universe.
There are some problems you can set in computing
that just are not decidable
at all - not by any algorithm and one of the
great names in this was Kurt Godel -
in the early nineteen thirties - and the second great name for computer
scientists that linked
Godel's work with how computer programs worked
and with his Turing Machines, was Alan Turing. He wrote
a famous paper in 1936 about his Turing Machines
- referred back to Kurt Godel's work and basically said
"There are some things in computing
that are undecidable" But for the moment
were coming in here, at the next level above Primitive Recursive
We're going and take a look at a Recursive function where
I can reason through with you that it will give
an answer. It's not in the nasty set above it,
the Recursively Enumerables, where sometimes it would go wrong
and just end up spinning and not doing anything useful.
This thing - and this is a good introduction as well to the way that
theoretical computer scientists
- of which I'm not one - but I'll try and give you the flavour about how you can reason about programs,
and how they behave, even without actually executing them.
The version of Ackermann's function that tends to be used nowadays - the one modified by Peter and by
Robinson: here is where all the hard work occurs
This is the recursive function itself We declare 'ack',
for short, a function with two incoming integer arguments.
And here, look, it delivers back an integer result
It delivers back the integer result in its local variable
which it declares for itself for holding the answer and eventually of course,
look, it's going to return
the answer. But how does it do its recursive horrors?
If the incoming argument 'm' is 0
then deliver back the integer answer 'm + 1'
So if I came in with ackermann(0,2)
because the 'm' is zero, it would deliver back
two plus one : three. Easy. Otherwise if that isn't true - if 'm' isn't zero, if it's any other
integer, else if 'n' is 0
then the answer is what you get by calling up ackermann, recursively again,
but this time by reducing the first argument by one. Call up
ackermann with 'm - 1', not 'm', and with
the first argument 1. Otherwise - now that's
bad enough but here comes the real killer - if 'm' isn't 0 and if
'n' isn't 0, what's the general case? The general case is
that the answer is ackerman of 'm - 1'
notice you're reducing 'm' again, look, and this is where a headache starts to
set in, this blows your brain and makes you realize why you can't
de-recurse this into iteration - the second argument for that generalized call
of ackermann, is itself a call of
ackermann! So you have to go through endless
thousands of stack frames to calculate just what the second argument must be
to another call of ackermann that's gonna go through the same agony
all over again. Now I think you can mentally visualize just what a huge
amount of computation
might be involved here and how big
the numbers might get to be. But what I would like to just
draw your attention to, because this is important,
is that every time 'm' and 'n'
are altered, in going round recursively, they
reduce. We found out that on the second line it says if 'n' was zero
then it called up a thing with ackermann( n-1, ...) in it
yeah, so you're reducing 'm' in that place
and even in the horrible worst case, the third line,
you reduce the first argument to 'm - 1'
and within that vile second argument
it's ackerman(m, n-1)
so as you go around this if 'm' and 'n' change at all
they are reduced. Therefore
if your first two traps,
which we've got here, are for when 'm' gets down to zero
and when 'n' gets down to zero then
in the end it will terminate, so long as
you feed in positive integers for 'm' and 'n'. Now, as ever, I have done no
error checking whatever - that's down to you.
I want you to concentrate on this. Yeah, if you put negative numbers in there, boy
are you in for a rough old ride !
Yeah, it's got to be
positive integers, zeros are fine, but must be zero or positive integers.
Although this is a huge recursive mess,
with millions of stack frames, nonetheless
by reasoning and saying that when these values are altered they
always alter downwards, you can convince yourself that this will
eventually deliver an answer.
Now, the only trouble is that, in delivering an answer, there may be a huge amount of
computation involved
particularly when we get into this third line and you have to run Ackermann's function
in order to work out what an argument to Ackermann's function is going to be.
And just to show you how bad this gets
I've set up two nested "for" loops on 'i' and 'j'
taking 'i'from 0 through to 5 actually, because it's 'i' less than 6
'j' from 0 through to 5, and I call up
the Ackermann function as the argument to be printed
in the standard piece of text here. So you get things like ackermann(0,0)
is whatever, and you call up ackermann
recursively, to work it out. ["So, how's that going for you?"]
How is that going for me?! Well, what Steve and I
(Dr Heartbleed as we now call him ....)
We set this going four weeks ago nearly, now.
The first few have vanished off the top, You'll be delighted to know that
ackermann(0,3) has a value
of 4, that ackermann(2,2) is 7
ackermann(3,2) is 29 - doesn't look too bad.
Now it did have a bit of a gasp for air
between 4,0 which is
13 and it finally decided that ackermann(4,1)
was 65,533.
It still took it, recursively,
on this machine, 3 minutes to work out
that ackermann(4,1) was 65,533
so this is progress, because this of course is a
fairly modern quad-core Pentium, or whatever it is [Note: actually a Pentium 4] running Linux.
The previous machine I had, when I first tried this, seven or eight years ago,
was a venerable Sun SparcBlade and the SparcBlade -
miracle of its age - took 20 minutes to work that out. So twenty minutes, three
minutes, we're progressing.
And then, do you know, I was looking at this with Steve
we've set the thing going - it's still running. And I said: "Oh!, y'know, it probably
won't be that bad, it'll be ...
if it took three minutes to work out something whose answer was 65,533
it'll take about, maybe, sixty five thousand
times three minutes to work the next one out
and did a few calculations - yeah, about four months on this machine.
something like that". Er, no!
I've just looked into it more deeply and reminded myself of the appalling properties
of the Ackermann function when it starts to build.
No, it will take two to the power
of 65,533 -
times three - three minutes per go. It will take three
times two to the 65,533
minutes, to work out that value.
That is unimaginably huge! It's no good saying it's 'astronomical'
- it's way beyond astronomical. The number of particles I think including all dark
matter isn't more than about
2 to the 300 - something like that - the number of seconds since the Big Bang is probably about
two to the 500 or 600 at most [Note: actually it's about 2 to the 59]
not 2 to the power of 65,533.
But what's gonna happen eventually - 2 to the power of 65,533
is such a big number, so we're going to start getting wrong answers. We'll either get
overflow happening or perhaps if integer
overflow isn't signalled to us - you know integer numbers sometimes tend to roll
over the top and go
negative. So who knows what will happen. I'll probably stop this off now
when we've made this video because frankly I have not -
I don't think I'm going to survive for two to the power of 65,533 minutes
- multiplied by three - for this to come to an end.
I think the astronomers would probably say the Big Crunch, when the universe all
gets down to a dot again, even that is probably
going to happen in about another 2 to the power few hundred ....
This sort of behaviour is often called 'super exponential'.
One of the ways of indicating that a function probably has to be done
recursively and can't be done in "for" loops
is when it starts behaving super exponentially
Not just like 'n' to the power 'n', which would be exponential
but 'n' to the power of 'n' to the power of 'n' to the power
of 'n' to the power of 'n' - done 'n' times
And your brain just collapses and refuses to even contemplate what that means.
In fact I've noticed one commenter - thank you whoever it was -
when somebody said: "Surely you can do anything in "for" loops? What do you have
to do
totally recursively?" Somebody has picked up one of those numbers I don't know much about
really big ones called googles and googleplexes - they've day been covered in Numberphile -
and said
How about ackermann of g64, I think it's called [Note: g64 is actually Graham's Number]
How about ackermann(g64,g64) ? The arguments before you ever start inflating them
are still absolutely astronomical but
the really interesting thing is that although we can never know what the
answer is
and the answer two to the 65 thousand whatever
divided by three, that is going to involve 20,000
decimal digits when it finally comes out
way beyond the Big Crunch, but
by reasoning with the program in the way we did we know
it is not uncomputable. Think back to the original hierarchy;
because we can never know the answer to some of these values
does it mean it's uncomputable? No- 'uncomputable' means there
is no algorithm for doing it. Ackermann is a perfectly good algorithm!
You can prove it terminates - it's just that none of us are going to be around long enough
to find out what some of those values are.