We continue with our discussion from
previous class, but what we want to

concentrate on is the notion of recursion
from a computer theory perspective.

So the approach that we're about to take,
which Martin Davis develops in his book

and is in all computer theory books,
at first glance will seem different than

perhaps the recursion that you may use in
programming.

And whether or not that makes a difference,
we'll discuss in a different lecture.

Anyway, a very simple recursive code for
factorial on lines four through nine.

Int fact, right?

Factorial returns an integer and it
accepts as input a number.

If the number is less than zero,
return minus one.

Minus one here would be a flag to indicate
something went wrong because factorials is

not defined for values that are negative.

We've mentioned that.

And when we discussed
partial functions, that

was on our list of partial
functions technically.

That the way it's officially defined,
it's not defined for negative values.

If it's zero, you return one.

That's the official base case.

It happens to be that factorial of one is
also one.

So some people will say that if it's equal
to zero or one.

But if you wanted to be pure about it,
then the base case would only be one.

Then you return the value one.

Else return num times fact of num minus
one.

And that's the official definition of
factorial, which you are familiar with.

Okay, good.

So, and that's recursive to the base case,
et cetera, et cetera.

And then you get your factorial value.

I'm pretty sure all of
you have done recursive

code somewhere in
your computing careers.

Anyway, so the above code is a top-down
approach.

What do I mean by top-down?

That you start with the number itself,
and then you work your way down to zero.

You work your way down to what is
colloquially called the base case.

But recursion in computer theory is a
bottom-up approach, as we will now explore.

You start with the base
case zero, and you work

your way up to the number
that you're looking for.

Or the, you know, it's the level for the
number you're looking for.

Is there a difference?

We will discuss in a different lecture.

Okay, so we're going to
take three very common

mathematical functions
that you're all familiar with.

And we will use the theory way,
primitive recursive theory way,

of describing them or implementing them.

Now, why do we need to implement them?

So remember the context
that primitive recursive

was trying to develop
a RISC chip, right?

A reduced instruction set computer chip.

And they want to... Again,
they didn't have a computer.

So they're interested in developing or
suggesting, finding really, the least

amount of methods, the
least amount of functions

you need in order for a
computer to be created.

So if they could show the least amount of
functions, then that would mean that the

requirements in order to build such a
computer would be that much easier because

you will only need a few instructions,
a few commands built in.

So we had commands before.

And those commands are...
We had those commands before.

We had...

We mentioned n, s, and u, right?

We had the null function, which always
returns zero.

We had the successor function,
which adds one, very simple.

And then we had this little bit
mysterious.

It's not really, but it's a technical one,
the u function.

I'm only going to use it once in the first
round when we add, when we build addition.

But I'm not going to use it again,
the u function.

And all the u function does is you...

Pardon the pun.

You give it a sequence
of values, a vector, or

a number in the
parameters of the u function.

You put in any number
of parameters, and then

you extract an element
from those parameters.

The simplest way to relate to it is
perhaps thinking of a one-dimensional

array, where you have a bunch of values in
the one-dimensional array, and then you

give the index of which value you want
back.

So that's the u function.

The actual role, as I mentioned last time,
is because they dealt with a technical

philosophical problem, is
how do you have access to the

inside of the parameter list
of the method you're calling?

How do you have access to the inside of
that?

So they came up with this function in
order to grant you that access.

Anyway, let's deal with it.

So addition of x and y.

Okay.

So now, again, we only have successor.

We only have plus one.

We don't have plus x or plus y in this
case.

So they needed to create to show that just
by having plus one and using the technique

called recursion and, again, composition
of functions.

And composition of functions means that
the output of one function is the input of

the next function, sort of a daisy chain,
a pipelining of functions.

When you pass each one, one takes an
input, provides an output.

That output becomes the input to the next
function in the list, right?

Et cetera, et cetera.

And you keep on doing that.

That's composition.

Now, this notion of recursion,
which we talked a little bit last class.

We gave them a little formal or abstract
technical definition.

Let's use it in practice.

Anyway, so add of x comma 0.

So then the question becomes how...

And so if you add x plus 0, that's x,
right?

We all know that.

But how do you get that x?

The x is embedded in the parameter list.

So of add of x comma 0.

That was the reason they developed...

That's why they provided this u function.

U of 1 comma 2, that's the name of the
function, means that you have two

parameters and you want the first one
back.

So x and 0 are the two parameters to add.

You want the first one back, which is just
x, right?

Your x and 0 are the parameter list,
and now you want the first one back.

You want x.

So all that's simply saying is that the
base case of adding 0 to x is x.

No big deal.

Now, let's talk about the general,
quote-unquote, recursive case.

So add of x comma y plus 1.

Now, this also may not be something you're
used to yet.

But in the top, bottom-up approach that
computer theory uses, it's not in terms of

y, it's in terms of y plus 1.

It's not in terms of n, it's n plus 1.

For example, the factorial would be in
terms of n plus 1, not fact of n.

It's no big deal.

There's a reason why they do this.

It's a technical, not a technical reason,
logistic reason, really.

It doesn't affect our discussions.

But just make note of it that I want to be
consistent with Davis's book.

And, in fact, how other computer theorists
do it.

Anyway, so as I said, it's really the top
case is x plus y plus 1.

And since you're at the level,
you're about to compute y plus 1.

So you previously in the recursion have
computed y.

In order to get add of x comma y plus 1 in
cell C16, what information do you have?

Well, you have add of x, y, right,
as in cell D16.

Why do you have add of x, y?

Because in the recursive definition, you
have access to the previous level's output.

And if you're currently at level y plus 1,
the previous level is y.

So add of x comma y plus 1, the previous
level is add of x comma y.

That's the output of the previous level.

But we need to do something to it.

Well, we have successor.

We need to build it.

That's built in.

Again, the null function, n, all it does
is return 0.

That's the letter n.

S, as we're going to use in line 19 in the
moment, the different function.

S, which is successor, which means plus 1
that we have here.

And then we have that u function technically
in order to access elements from a list.

Anyway, which we're not going to use because
people drop it eventually in notation.

Again, it's technically there everywhere.

But in notation, they drop it because it's
too messy.

So on line 16, add of x, we're adding,
what are we adding to x, y plus 1?

That's defined as, well, if you can add y
to x, now just add 1 to that.

And then, in fact, you
will get the mathematical

definition or equivalent
of adding y plus 1 to x.

Okay?

And that's noted in the comment in cell
I16.

All right.

So that is how you add.

Add is recursive plus 1.

Recursive plus 1 is s.

All right.

Good.

So that is in the case of add.

Maybe I'll just put that comment in for
us.

Let me just add a few short comments.

Add this flag to indicate...

To indicate something went wrong,
but to indicate a value where not...

An input value where not defined.

Okay?

And this is what is colloquially called
the base case.

And this is the recursive step.

Okay.

Recursive step.

Note, the level to be determined is n in
terms of level n minus 1.

All right.

All right.

The level to be determined is...

What did I say?

Is... Well, in our
case, it's num.

In terms of level, num minus 1.

All right.

All right.

The... Okay.

Above we mentioned.

Yes.

So over here, I want to make a comment.

And simply add is recursive S,
which stands for successor.

Good.

All right.

So that's addition.

All right.

You know... Well, we could.

I guess... I'm
thinking of doing this.

Okay.

Fine.

Give me one second.

We used to... What's...
Give me one second here.

Years ago, we used to have a concept
called playing computer.

Just trying something.

Playing computer was
a way of simulating a

computer computation
using pencil and paper.

And the way you would play computer is
simply you lay out all the relevant

variables and methods and what you expect
to happen.

Okay.

So you... Oh, I'm sorry.

Let me just do one more thing.

Level.

Level.

So at level zero, the base case...

Okay.

We'll do a bunch.

A few.

I'm sorry.

We'll do a few.

So you get a gist of what's going on.

Okay.

So what's happening?

X is always X.

That's...

What I mean is...

That's... Although we
call it a variable, that

value is not going to
change from level to level.

Okay.

That was the base... That was
the... That was the... The basic input.

Right?

The level... What's
going to change is Y.

What level of the recursion you're up to.

Y is going to change.

Initially, Y is zero.

And then Y will become one, two,
three, four.

In this case, five.

All right.

So what happens?

In the base case, add of X plus Y is X.

Right?

Because that's the... It's
X... That's the base case.

That's the definition.

That is... So that was the...

The U function was the H.

I think we used the letter H last time.

The generic function that computes the
base case.

But now we have... I'm sorry.

Give me one second.

Okay.

I think we did it slightly differently.

Well...

The question I want to put is whether I
should put this over here.

Give me one second.

Oh.

The question is how many...

The question is how many columns should I
do in order to make this work?

All right.

Let's do it this way.

At this point, add of X, Y is zero.

Is X, rather.

And this is not applicable.

Okay?

It's not applicable.

There is no successor of add X,
Y at this level.

Okay.

Now...

In subsequent levels, the add of X,
Y is going to become the next level.

So let's take the next level.

So now it's Y plus one.

So we have...

Wondering... Okay.

So the previous levels output at this
point...

The previous levels output
at this point... Oh, okay.

So... Okay, wait a second.

All right.

Hold on.

See, if I mean it like this...

Previous level.

So there is no previous level.

And this is the future level.

Okay.

Maybe that's better.

Okay.

So for the base case...

And then final value.

Okay.

Fine.

Ah... That's not too good.

Ah... Well, we'll
call it final value.

Fine.

Let's see how this works.

Let's see if it makes more...

If I'm making things worse than it is.

All right.

So our final value is X.

All right.

The previous level is then going to be
equal to whatever that final value is.

The previous level...

In other words, once we do the next level,
that automatically is the previous level.

Right?

So that's going to always be whatever that
last value is.

Now we're going to add 1 to it.

So that's going to be our final value.

Now we're going to add 1... So now at
the next level, we're going to add 1 to it.

And that's going to be our final value.

In this case, this is our final value.

Right?

Why isn't it centered?

All right.

And then we're going to
add... we have x plus 2, and

now we're going to add
1 to it, so it's x plus 3.

And then we're going to add 1 to x plus 3
at level 4, and that becomes x plus 4.

And finally, we're going to add 1 to x
plus 4, and we're going to get x plus 5.

And that's going to be the value at the
end of this recursion.

All right?

All right, now.

Final value, output.

Okay, let's call it output.

That's not bad.

All right, let's do multiplication.

Let's do multiplication.

Give me one second.

Okay, fine.

Let's do multiplication.

I was just wondering maybe I should give
it an actual value for x.

But that makes things a little bit neater.

I don't know.

All right, let's do multiplication.

So, oops, sorry.

So mult of xy.

So mult of xy, mult is recursive addition.

At this point, at this point, we have
addition.

So we can now use it forever.

Once you have, once you've proven,
once you've proven that a function is

recursive, so then you
can use it at that point on as

part of your repertoire of
building other functions.

Okay?

So now, so mult of x, 0.

When you multiply x times 0 on line 30,
that's n of x.

That's just 0.

Right?

Anything times 0 is 0.

When you multiply x with y plus 1
recursively.

So that's based on having the previous
level's value of mult of xy.

And you add to it one more x.

And that would be the equivalent as if you
multiply x, y plus 1 times.

You multiply by y plus the one other x
plus x.

And that uses addition, which we just had.

So using the same system here...

Let's play computer, and
let's see a little bit what

the simulation would
look like with multiplication.

All right?

So we have add, so that's going to be
multiply.

Okay?

Now, the function is add... it's a little
bit longer.

Anyway.

Let's see here.

Curious if I use wrap, whether it'll look
decent.

It looks not too decent, but it's not bad.

Well, all right.

So now we have add of mult.

Maybe not.

Maybe I shouldn't have done that.

Okay.

Let's expand that.

No choice.

Okay.

So then... And then the
result will be mult of...

x of y plus 1.

All right.

So let's get started.

So when you multiply...

When you multiply x times 0, that's 0.

Now, when you want to do mult of x comma
1, that's mult of...

That's add of mult of x comma 0 and x.

So the previous level's output is 0.

And now, what's the result?

So we're adding to it x.

Okay?

The next level, the previous level is x.

But now we're adding to it another x.

Now, at the third level, mult of x,
y, the previous level's output is 2x.

And we're adding to it an x.

The next level
is 4... Is level 4.

The previous level's output is 3x.

And we're adding to it an x.

And in our example, now in level 5,
the previous level's output is 4x.

And we're adding to it x.

So we end up with 5x.

Okay, an important little note here.

An important note that we have to consider
is the following.

And... Oh, no, it's not yet.

It's for power.

Okay.

All right?

So that's multiplication.

One more, and then we'll talk a little bit
about this.

Power.

Why did I do it that way?

Interesting.

Maybe it's not a bad idea.

Okay, one second.

Not bad.

All right.

Let's do power.

All right.

So power of x, y.

Exponentiation.

Now, power of x to 0.

Anything raised to the 0 is 1.

Now, technically, there is no function
called 1.

Everything has to be a function.

Technically, it's the successor of n of x.

Right?

n of x is 0.

Successor is 0 plus 1.

And that's the number 1.

We mentioned that last time.

We mentioned in order to get any number
of...

any fixed integer k, you would have to use
the successor k...

the successor function
composed with itself k times

s of s of plus 1 plus 1
plus 1 k times of n of x.

Because the starting point is 0.

All right?

Anyway, so power of x to the 0 is 1.

We'll mention...

There's a note here that's important,
which we'll mention in a second.

And then... So
that's the successor.

And now, in general, the power function
will be x to the power of y plus 1.

x to the power of y plus 1 is as if you
multiplied x to the power of y times x.

Power of xy is the previous level's
output.

You are allowed to use it.

And mult is now a function that we showed
is recursive or primitive recursive.

All right?

So let's play computer.

And we'll mention our note in a moment.

Yeah.

Okay, fine.

I'm doing that.

Let's see if this works.

Yeah.

All right.

So now, let's play computer.

So now we're doing power.

So power of xy.

And that's going to be the mult.

Multiply power of the previous level's
output times x.

And the result will be the future,
which is power of x.

x raised to the power of y plus 1.

All right.

So let's get started.

x to the power of 0.

The base case is 1.

Now 1.

So what are we doing?

So power of x to 0 is 1.

And now we're multiplying 1 by x.

So that's x.

Next level 2.

The previous level's output is x.

But now we're multiplying it by x.

So we get x squared.

On level 3, we have x squared.

The previous level's output.

But now we're multiplying by x.

So we get x cubed.

So maybe I should do that.

Give me one second.

I think what I should be doing is the
following.

Interesting.

Give me one second.

Yeah, I think maybe I should be doing the
following.

I think I should be more explicit as to
the fact that this...

the future level's based on the previous
level's output.

So maybe if I do it this way...

Oh, yeah, that won't work.

Oh, that's a shame.

Why did I do that?

Yeah, that doesn't look as good,
though.

That would not look as good.

But okay, fine.

So then I'll have to change this manually.

Give me one second.

Let me think.

Yeah.

All right.

So I'm trying to emphasize here that it's
the previous level's output.

But over here, we don't need to.

All right.

So you know what?

I don't have a choice.

Give me one second.

I want to emphasize that on column F,
it's the previous level's output,

whereas in column G, it's the actual
result.

So now it will be...

in order to be X plus X.

It'll be... Here.

It'll be X plus X.

I'm sorry.

It'll be 0 plus X.

Okay.

Oh, that's interesting.

Yeah, I could have done it that way.

Oh, that's what I meant.

Oh.

Even better.

Give me one second.

Even better.

It's equal to...

Yes.

That's it.

Good.

So then this...

Whoa.

That was pretty cool.

But that's not what I want to say.

What do I want to say?

So that would be 0.

So that would be previous.

0 plus 1.

And that would be 1.

That would be...

No.

Hold on a second.

No, no, no, no.

Not plus 1.

It's times X.

Sorry.

Hold on.

What am I doing?

It's plus X.

There we go.

And that would become X.

And then this will be...

Yes.

Good.

And that would be 2X.

And then this will be...

3X.

And that would be 4X.

And this would be 5X.

Good.

I think that may be a little bit cleaner.

All right.

So let's do it here.

What would it be?

It would be multiplying.

That plus would be times...

Yeah, that didn't work.

Yeah, I'm sorry.

And that would be X.

And that would be X squared.

X cubed.

X to the 4th.

X to the 5th.

Good.

Oops, sorry.

X to the 5th.

Good, good, good.

All right.

So I think that's hopefully a little
cleaner.

All right.

Good.

So that is the story.

So that is the power function.

All right.

Now, the first comment is a comment we are
ready...

that I'm about to make is a comment we
made before.

The second comment is innocent,
but a doozy.

And it's not something we're going to be
able to answer right away.

Even though you think we should be able
to, but we're not.

But it's going to be pretty powerful.

Anyway, so here's
something surprising is about

to happen with this
simple thing we just did.

All right.

First, the regular note.

The note that we mentioned once before.

On line 53 note, it is because of this
base case...

Of this base case.

It is because of this base case...

Let's put an asterisk here.

Okay.

So that's the base case we're referring
to.

That power of x to the 0 is 1.

It's because of this base case...

Maybe I'll fill this in so you realize
that that's the note.

And then I emphasize the 1 here to show
you that point.

It's because of this base case that Davis
defined 0 to the power of 0 equal 1.

Because he needed it for power of x to the
0 is 1.

And that's the appropriate base case for
all further recursion.

All recursive levels using the base case
of power of x comma 0 is 1 makes sense.

And you need a total function in computer
theory.

You need every memory configuration to work,
to be effective, and not have a problem.

So, therefore, it is
because of this base case

that Davis defined 0
to the power of 0 is 1.

Even though mathematics
states that 0 to the

power of 0 is indeterminate
and cannot be defined.

Davis had to do this since all primitive
recursive functions must be total since

they were an attempt to model all
computable functions which are total.

Remember that Turing maps a
memory configuration called the

input to another memory
configuration called the output.

The value 0 has a valid memory
configuration as an input as an input,

the value 0 has a valid memory
configuration, a string of 0s.

So, it had to apply.

Again, what are we doing here?

We're trying to create a computer and
we're trying to... they don't have one yet.

So, they're trying to do it and they're
saying to themselves, let's make our...

on the first draft of a computer,
let's make our lives easier.

How do we make our lives easier?

We're going to build a risk computer,
a reduced instruction set computer.

We're going to build it so that we have
the least amount of functions that you and

I need to build in the hardware.

And then we have a computer, and then
we're going to have technology,

the methodologies of...

or technology of
composition and recursion,

which they also have to
build into the computer.

And from there, you'll be... they hoped
you'd be able to compute any possible

computable function.

And the initial attempt was called
primitive recursive.

That was the initial attempt to this
experiment, something that eventually

Davis proved, and others as well,
that, in fact, it didn't work.

Not that there's something wrong,
and it's not sufficient.

You cannot achieve all possible computable
functions, all possible total functions,

by using primitive recursive alone.

And the question will be eventually,
what's missing?

All right.

The other issue... okay, let's do one
more, just for the fun of it.

I just want to be consistent in how we
presented it.

And then we'll ask questions to ponder on.

So one of them, at least one of them is a
doozy.

Really, really innocent, but incredibly
hard to answer.

Well, let's see.

I don't want to say that to you yet.

All right.

Let's do factorial.

Let me get this going.

All right.

Factorial.

One more.

Factorial.

Fact of x comma y.

Good.

What's the story with factorial?

The base case is one.

That's how it's defined.

The base case is zero.

Zero.

Factorial is one.

Good.

Again, technically s of n of x,
but we'll ignore that for now.

All right.

As we mentioned here.

All right.

And now, x factorial...

No, sorry.

What we're doing is we're taking y...
We're taking... Wait a second.

Who are we taking?

Y factorial times y plus 1.

And that's, in fact, equal to y plus 1
factorial.

Okay.

We're taking the previous levels output.

We're multiplying it by the next number.

And we're getting the next factorial.

All right.

And that's what we're doing.

Previous levels output.

Fact of y.

It's a one-parameter input.

Again, even though you may be used to
saying x or n, here being consistent,

Davis has to say y.

Because remember, the x does not change.

Only the y changes.

So it had to be facts of y because the
fact of y, factorial of y, because y is

the variable holding the level number
level by level.

All right.

Now, why did I do that?

Huh.

I'm not sure.

Better served here.

Okay.

Now, so let's go through this.

So 0 factorial, in fact, is 1.

Oh, so there is no x.

Ha-ha.

One second.

We have to change this a little bit.

We have to unwrap the merge.

We have to merge your map here.

Good.

All right.

Input.

No plural.

Input.

Singular.

Input.

That's why I did something like that.

I don't know.

Input.

Just like being consistent.

Good.

All right.

So let's do that.

So 0 factorial is 1.

And then we have 1 times... well,
instead of x, it'll be 1 times y plus 1.

Oops.

Sorry.

I'm subconscious.

Vectorial.

Okay.

Y plus 1.

And that'll be equal to y plus 1.

All right.

The previous level's output is y plus 1.

Oh, that's going to be weird.

Give me one second.

Yeah.

Give me one second.

One second.

It's true, but that's going to be a little
odd to understand.

Give me one second.

Oh, boy.

To hear the y plus 1 is an actual value.

That's going to be confusing.

The y plus 1 is 1.

Yeah.

That's going to be confusing to you.

Give me one second, please.

Oh, boy.

I guess I don't have a choice.

Okay.

We're going to have to do it like this.

All right.

So then, it's y is the level that we're
previously at.

And plus 1 is the next level, y plus 1.

And the next number, that's 1.

And then it becomes 1 times 1 plus 1.

The previous level.

And that will become 2.

And that will become 2 times 1 plus 2.

1 plus... 2 plus 1, sorry.

And that will become 6.

And it'll be 6 times 3 plus 1.

And that will become...

I'm sorry.

Wrong one.

That will be 6 times 3 plus 1,
which will become 24.

And then, finally, 24 times 4 plus 1,
which will become, in this case, 120.

All right.

So, hopefully, I mean, feel free to follow
this, you know, along going level by level.

But that gives you a little sense of
what's happening here.

All right.

So, again, just to review what we do, we
show that addition is primitive recursive.

Again, we... Okay.

So, maybe we should make a statement here.

Remember that...

Primitive recursive...

Okay.

Remember that.

Okay.

Let me write a little bit.

Just to remind you again what primitive
recursive is.

Remember that primitive recursive was an
early attempt to model all computable

functions using a RISC chip, as it were,
reduced instruction set.

The original hope was that the computer
that they had not yet built

would only require a few
functions and techniques, a few

of what they call the initial
functions and techniques.

And yet, achieve all possible
Turing-equivalent computations.

Okay?

Again, they didn't... It was a
nice idea and they got pretty far.

This is... The primitive
recursive model is incredible.

It gets really, really far.

But it's not the answer.

It's something's missing.

We'll talk about that, as I said,
a different time.

Now, let's just say what those initial
functions are.

What the techniques are, just to remind
you.

The initial functions used...

We have N.

N of X always returns zero.

S of X returns plus one.

And then we have U sub i of N

returns the i-th element from a list of N
numbers.

But again, you had to give those numbers.

So, it doesn't really do...
It doesn't change anything.

It doesn't change values.

Okay.

The techniques used...

The techniques provided were
composition...

And recursion of sorts.

And that recursion is what we're trying to
discuss now.

That's what we want to try to discuss.

What was that recursion?

And that's why we're going through this.

So, we have some basic functions.

Not much.

And then we have these techniques.

And from there, we could build addition.

From there, we could build... Once we have
addition, we could build multiplication.

Once we have multiplication, we could
build exponentiation or power.

And we threw one more in, factorial.

Just to give you a sense that we could
get...

A lot of things can be done in this
manner.

A lot of things can be done in this
manner.

All right, now, some important questions.

Four questions to ponder on.

Okay, one.

We start with 0, n of x, and we add 1,
s of x.

All functions seem to be increasing.

Where is predecessor, which subtracts 1
and is the basis for subtraction?

Good question.

Everything seems to be increasing,
right?

N of x just sets it to 0.

s of x sets it to 1.

u just retrieves some values that are
already there.

It doesn't change the value, right?

It doesn't

change any values.

It just returns a value that's already
there.

So where is subtraction?

Where's minus 1?

Where's subtraction?

Similarly, we have multiplication.

Where's the division operator?

To whatever extent.

Okay, so, you know, it's...

To whatever extent...

What I mean by that is...

To whatever extent that integer division
can accomplish.

Okay, because we're only dealing with
integers.

Because the memory configuration is only
an integer.

But whatever that is, however you want to
define it, where is it?

How come we can't do division?

Question number three.

And that's what we mentioned above.

If one recalls how we program factorial
and actual code, the main recursive call

is n times fact of n minus 1, which is a
top-down computation.

But all primitive recursive functions are
bottom-up.

Starting at base k0 and then computing the
next level, y plus 1.

Are these the same process?

Okay, so that I alluded to and mentioned
sort of above.

Now comes the dinger.

It looks like it's a simple problem,
but as I wrote over here, hint,

this is a much harder problem than it
seems to be.

So if you're in the mood, don't answer
now.

You either knew the
answer before you started,

in which case, let
others think about it.

And if not, I hope you'll
forgive me, but I can't believe

that anyone's going to figure
out the answer right now.

So email me.

In either case, email me if you ever think
of an answer.

Okay, email me at the class-designated
email cs722projectsqc.

Anyway, question number four.

We will show that each
recursive function, similar to any

of the above, can be
implemented by a single for loop.

So the iterative process
of addition, which is

based on successor, can
be replaced by a for loop.

Multiplication can be replaced by a for
loop based on addition.

Exponentiation, power, can be based on a
single for loop based on multiply.

So in essence, we have a triple for loop.

Okay?

We will show that each recursive function,
similar to any on line 94, similar to any

of the above, can be implemented by a
single for loop.

So power is recursive multiplication.

Multiplication is recursive addition.

And addition is recursive successor,
will produce a triple nested for loop

code, only using built-in commands such as
n of x equals 0 and s of x equals x plus 1.

We know from analysis of algorithms that
built-in commands, as opposed to library

calls, to library calls, slash APIs,
even if they are built-in.

We know that the built-in commands have
complexity, have time complexity constant.

The built-in commands do.

So we can assume, and it's correct,
that n of x and s of x, when you build

your computer, is going to be,
in fact, constant time.

What is the true complexity of this code?

Is it order of n cubed?

We have a triple for loop, right?

We have a triple for loop.

What's the triple for loop?

Addition is recursive successor.

Successor is built-in, that's constant
time, and now you have a for loop.

So you would think addition is order n.

Now you have multiplication is recursive
addition, m or n times, whatever.

So that colloquially we would think is n
squared.

That's multiplication.

Now comes power, and that's recursive
multiplication.

So shouldn't that be order of n cubed,
right?

It should be straightforward.

It should be very simple.

Well, believe it or not, it's incredibly
hard to answer that question.

Whatever the answer is, even if it turns
out that the answer is n cubed,

it's not simple.

Whatever you think, it's not simple.

Trust me.

Or don't.

Either way, it's fine.

But whatever you do, think about it and
tell me if you could show, explain by email.

Don't do it now.

If you could explain what complexity you
think it should be.

All right?

So that's a homework which I'm not going
to answer.

Well, we are going to answer, but I'm not
going to collect.

We're not going to answer right now.

We have to do other
things to do first to get

a better sense of what
this recursion does.

And a better sense of computer theory in
general in order to answer this question.

But believe me, it's a much harder
question than meets the eye.

All right.

So that's the basic command.

So we did addition.

We did the multiplication.

We did exponentiation power.

And we did factorial.

All right.

Now, Davis continues to show you how
powerful this approach is.

All right.

But at the end of today's lecture,
well, I don't know if at the end of

today's lecture, at this point,
but it may be next lecture.

At the end of our discussion

on primitive recursive, we will get the
impression on just how expressive and

powerful primitive recursive functions
are.

Ah, so this is what I mentioned before.

I don't have to repeat it.

All right.

So, well, I can leave it in here.

All right.

Well,

you know, let me pull this out.

Let me pull this out.

I may include it,
but this is... Okay.

Let me pull this out for now.

It's... There's a nuance here, but it's
mainly redundant to what we just said.

So, it's not worth it.

Not right now.

I'm sorry.

All right.

The point...

Part of what I was going to say is that
some of it we're about to answer right now.

So, we're about to answer the first
question.

One of the questions we had was...

The first question we had is, where is
predecessor?

Which subtracts one and is the basis of
subtraction?

So, this is quite interesting.

It's a sharp answer.

Davis gives a really sharp answer.

Where is predecessor?

Because all you're doing is you start with
zero, you add one.

Right?

And then the...

What you call it?

The S... The S
function adds one.

The U function just returns values you
already had.

It doesn't change value.

Right?

So, that's... Where's
predecessor?

So, here we go.

I thought I numbered these.

Huh.

I thought I numbered these.

Give me one second.

I really would like to number these.

I would like to number these.

Okay.

So, how should we number these?

We'll call them this primitive number 1.

Where should we number them?

Give me one second.

Okay, I'll call this primitive number one.

Prim one.

It'll also make it a little bit easier in
case you want to reference them.

Prim two.

Technically, this is prim three.

Those are built in.

Okay, primitive number one.

We should say number one.

Maybe not.

I don't know.

Okay, whatever.

Okay, and this is primitive number four.

Then we have primitive number five.

Primitive number six.

Davis does number them.

I don't know if I'm doing the same
numbering.

In the beginning, yes, but eventually not
because I think he has one or two of these

as A and B of a number, and I'm giving
them separate numbers.

B and A.

This is number seven.

All right, so now we'll have primitive
number eight.

And that's the question about predecessor.

Primitive number eight.

Okay, so this is a really, really sharp
answer that Davis gives.

So ignore what I wrote for a second.

Let me tell you the answer.

If you recall everything we did with
recursion, right?

So we mentioned that we always are trying
to, it's a bottom-up approach.

We're always trying to compute the next
level based on the previous level.

So when we're at y plus, when we want to
compute y plus one, we have the previous

levels output, but we also have the
previous level, right?

In addition to having, in addition to
having, so what does recursion have?

As we mentioned, this approach,
this type of recursion has three,

we mentioned this last time, has three
categories of information at its disposal.

Disposal, for whatever purposes it wants.

Disposal means you can throw it away.

But there's a reason I say it that way,
because literally, and Davis points that

out, this is not an obligation.

The word disposal is very accurate here.

Disposal means you can throw it away.

This term is accurate
here to emphasize that one

does not, is not required
to use all the information.

information available.

To use all the information provided.

Okay?

So that, it's that, in that sense,
it's disposal.

Disposal.

At its disposal.

Okay?

There's no obligation to use all the
information provided.

What's the three categories available?

So the three categories are as follows,
and we, again, we mentioned this last time.

So, info number one.

Information number one is the static input
x.

The static input, which is variable x.

Information number two, level number.

What level are you up to in the recursion?

And that's variable y.

And then info number three.

And then info number three is previous
levels output.

Right?

Well, generically, rec of, rec of x comma
y.

Or in the case of multiple, that's the
single, that's the single variable version.

Multi-variation.

Multi-variable.

Multi-variable.

Well, yeah.

Multi-variable will be x1 through xn,
y.

And then rec of, x1 to xn comma y.

Okay?

Right?

And then the next level does what it wants
with these.

With these three pieces of information,
or three categories of information.

Namely, g, we said the letter g,
g of, g of, g of, well, how do you do it?

He, I think he put y first.

And I just want to be consistent with his
notation.

I think he does y first all the time.

Anyway, whatever.

Let me be consistent here.

Okay?

G has all those pieces of information at
its disposal.

And to emphasize that the
categories of information, I'll

put them in square brackets
just to emphasize that point.

And also because square brackets very
often means optional.

You can use what you want.

No obligation.

Okay?

Now, the key point here is the level
number.

So, if it's the previous level's output,
it's the previous level number.

See, the level number is previous.

Right?

You want to do y plus 1, but you have y.

Right?

The previous level's output.

The next level, y plus et, which is
parentheses, y plus 1.

Okay?

So, why is that significant?

Because from y plus 1's perspective,
y is the predecessor.

Which means that embedded in recursion is
the subtraction operator, the minus 1.

It's a sharp answer, but that's Davis's
answer.

That's Davis's official answer.

Predecessors.

So, let's get to predecessor.

First of all, 0 is the smallest number in
the memory configuration approach.

Because all 0's is the smallest in that 0.

There's no negatives.

You can interpret it as negatives however
you want.

But again, we're not dealing with values.

We're dealing with memory configurations.

So, the predecessor of 0 is 0.

That 0 is n of x.

The predecessor of y plus 1 is y.

How come?

G takes all the information given to it.

What's the given information?

Well, there is no x.

But there is y.

And predecessor of y.

Predecessor of y is the previous level's
output.

Right?

And what will you do with g?

The u function.

Just return.

Again, what information does this g,
which manipulates and provides,

transforms the categories of information
we mentioned to the next level's output.

It takes the three-piece information here
and there too.

Because there's only one variable in the
parameter list.

Y.

No x.

And...

I mean, that's... Well, okay.

Fine.

Here will be n of y.

There is no x here.

So, n of y.

Because we're dealing with y.

All right.

I'll leave it, quote unquote, x.

It's just generically called x.

There is no real x here.

G of y.

So, you have... G
can do what you want.

But what information do you have?

You have y and predecessor of y,
the previous level's output.

What are you going to do with it?

You're going to ignore the previous
level's output.

And you're only going to return y.

And that function is u12 of y and pred y.

Great.

I should put it in the world.

What is it appropriate?

G?

U of 1, 2 of y, pred y.

All right.

So, that's the subtraction operator.

Now, cutoffs... Oh,
so that's predecessor.

Minus 1.

What is the next?

We want to do subtraction.

And we got to be a little careful with
subtraction.

Because 3 minus 4 is minus 1.

And we don't have negatives.

There is no memory...

All the memory configurations are read as
non-negative integers.

So, how do we do subtraction?

So, you need what Davis calls a cutoff
subtraction.

Meaning, you can never be below zero.

You cut off the recursion if the output is
tending to be negative.

And you stop at zero.

And it's very often written as x minus
small o.

That's the icon.

The o... So, subtraction...
The o is meant to be zero.

To remind you that you can't get less than
zero.

So, the icon is minus zero.

Minus o.

That's just the icon used in the book.

All right.

Subtract...

Maybe I should do that.

Okay, fine.

So, what's the recursion?

Subtract x comma zero.

If you subtract zero from x, the base case
is x.

Right?

And then the recursive function is
simply... So, subtract y plus 1 from x.

So, that will be the predecessor of
whatever subtract of x comma y is.

And even if sub of x, y is zero, we mentioned
on line six that pred of zero is zero.

So, that's already built in a cut off.

You can't get less than zero.

All right.

So, that's the cut off subtraction.

All right.

What about... Oh, so
that's prim number eight.

Oh, sorry.

This is prim number nine.

Prim number nine.

And then this will be prim number 10.

Now, we're up to absolute value.

All right.

The absolute difference.

Although you can't have negatives.

Three minus four in cut off subtraction
will be zero.

But you could do the absolute difference.

Three minus four in absolute value is one.

So, a diff is just a composition.

A diff is sub of x, y plus sub of y,
x.

Why?

How come?

One of those is zero.

One or both of them is zero.

Well, if x equals y, then
subtracting zero from

x, you know, subtracting
x from y will be zero.

So, that won't change anything.

Let's say x and y are not zero.

Then one of them is bigger.

Let's say x is bigger.

So, then subtract of x, y will be a
positive number and subtract of y,

x will be zero.

Because it should be a negative number but
it's a cut off.

You can't get negative.

You get zero.

So, the end up will be, and same thing if
y is bigger.

If y is bigger, then the sub of x, y will
be zero because it's a cut off subtraction.

You can't get less than zero.

And since y is bigger, y minus x is a
value.

So you, in essence, get the absolute value
of the difference.

Even though you can't
get the negative in the

difference, you can get
the absolute value of it.

Okay.

Now, we have not equal to zero.

And I put an important note here,
which is that it's similar to,

akin to, the not in C-based programming,
where true is greater or equal to one.

All right?

So it's not equal to zero.

This is also a composition.

This prim number 11.

I should put a note here.

One second.

Composition alone.

You're also composition alone.

So not equal to zero is alpha of x.

That's the letter Davis uses.

Alpha of x equals one with the cutoff
subtraction of x.

Why is that true?

If x is zero, if x is zero, then one minus
zero is one.

If x is one, then one minus one is zero.

If x is bigger than one, then one minus
four is still zero because it's cutoff,

minus o.

It's the cutoff subtraction.

So the only time... So
the only time... the only

time that alpha will
be one is if x is zero.

All right?

All right, good.

Next one, equality.

So equality is prim number 12.

And that is composition alone.

Let's see how it works.

So take the absolute difference of x and
y.

And then... and then say alpha.

Right?

Equality.

So first of all, this is a Boolean we
should mention.

It's a Boolean.

It's a Boolean of sorts.

Returning only zeros and one.

Zero or one.

That's also equality.

All that's... all of these are Booleans.

All the different relationship ones here
are Booleans.

As I mentioned here, Boolean predicates.

All right.

We'll get to it in a moment.

Anyway, so equality.

So how does that work?

Sorry.

So equality works as follows.

X and y.

If x equals y, so then the absolute
difference x minus y will be zero.

Then alpha will turn zero into one.

And if x doesn't equal y, so then alpha
returns zero.

But then alpha returns zero.

But then alpha... no, sorry again.

Apologize.

If x equals on line 22 for equality.

If x equals y, then the absolute
difference a diff equals zero.

And then alpha returns one.

If x is not equal to y, then a diff is not
zero, in which case alpha returns zero.

So the only time zero is returned... the
only time one is returned is if it's equal.

The only time that eq will return one...
is if x equals y.

Okay.

Good.

Now what about less than or equal?

I'm sorry.

What about less than or equal?

I'm sorry.

This is prim number 13.

And this is composition alone.

In fact, a number of these...

All right.

I want to quickly check.

I think all of these, yeah, are all
composition alone.

I think maybe because it's sort of towards
the end of class.

Give me one second.

Sorry.

14, 15, and 16.

So then we did equality.

So then we will try to
read them yourselves,

but we will go over it
next time on Wednesday.

So less than or equal,
greater than, less than,

greater than, equal are
all compositions alone.

And then just a quick little thing here
about Boolean predicates.

Okay, you'll read this.

It's a question of Boolean predicates.

My point, though, is that from here, we're
going to get some more sophisticated ones.

And let me just... Maybe it's
not clear that these are further...

Obviously, I have to
update the numbering.

But these are further primitive recursive
definitions.

Oh, this is actually recursive.

All right.

Anyway, give me one second.

This is recursion.

This is recursion product summation for
all... Oh, no, that's composition.

All right.

Whatever.

Okay.

We're going to have to deal with this.

And then, eventually,
we're going to get to the

bounded minimization,
which is the gold star here.

That's our goal.

We want to get to the bounded
minimization.

Anyway, I'm going to send this to you so
you can read ahead.

But I'm going to point out in the notes,
we only got up to the end of equality.

All right.

So I'm going to put a little line here.

Just to remind you that that's where we
got up to.

Okay.

We'll continue with this next time.

If you didn't have a chance, please text
the word PRESENT.

And I will send you these notes this
afternoon.

And we will continue on Wednesday.

Thank you all for attending.

Sorry.

Again, if you didn't have a chance,
kindly text the word PRESENT.

Thank you all.

Bye now.

Bye now.