Hi there before we get started building our

CPU I thought it would be good to go through a little exercise showing what a computer

can and cannot do for you. A computer is a machine that will run algorithms , the questions

are can we create an algorithm for every mathematical question that we want and is there a master

algorithm that we could write that could potentially solve all mathematical problems. So that’s

what we are going to look at over the next 2 videos. Now in these videos I have taken

the liberty of already writing some of it out to save a bit of time. So one particular

algorithm that we could look at is finding the highest common factor between two numbers.

So if we take the numbers 3654 and 1365 , now we can find the highest common factor between

those by dividing the larger number by the smaller number and taking a remainder so if

we do that we get a remainder 924. If we then take the 1365 down and divide it by the remainder

924 we get 441 , we then take the 924 down divide it by the 441 and we get 42 then take

the 441 down and divide by 42 and get 21 , we take the 42 down and divide it by 21 and we

get 2 with a remainder of zero. So the highest common factor is 21. So that was the example

of an algorithm. We can draw it out in this format here, so we could take our 2 numbers

A and B we can go through this process where we take A divided by B and we get the answer

C , then ask the question is C equal to zero, if it is n’t then we go back up in here and

we replace A with B and B with C and we go back in to this point here and again run through

the A divided by B until eventually we get down to the point where the answer is zero

and at that point the final output will be B which will be the highest common factor.

Now the question that was asked by David Hilbert who was a famous mathematician is a question

called the Enstschadegung problem which loosely says is there some general algorithm for solving

all mathematical problems meaning can we have one master algorithm that

will solve all mathematical problems. Now a guy called Alan Turing came along and he

looks at that problem and he creates an imaginary machine. Now his machine looks like this . We

have a box called TM for Turing Machine , and the Turing Machine takes a ticker tape and

it’s an infinite piece of ticker tape and it sits in a box and it just goes on forever

and it acts on this ticker tape on it outputs it here and gain that end goes on forever.

So if you think about this ticker tape just holding values of zero and one. So let say

the initial value is 011010. We ll this machine here will take these values and will act on

them in some manner and the final output will be another set of values here . So in effect

this here just looks like an algorithm machine in the same sens that up here we take in an

input and we go round the algorithm , we get an output . Now here is an example of the

way he thought about it. If we think about an internal state of the machine (s) and an

input to the machine (I). If we have certain state and a certain input then what we can

is we can either retain the same state or change the state and we can retain the input

at the value or we can change that input now can then move one movement to either the right

or the left and take in the the next value. Now what is this internal state of the machine

? Well when we go to build the CPU we will see that we have registers and an accumulator

and program counter , we will have other things inside our machine that define how our machine

operates. At any one point in time you can take a snapshot in time and you can look and

see exactly what is inside the machine at that point in time or exactly what the state

of the machine is at that point in time . That is all I mean by the term internal state.

So lets go through these examples here . If the machine was is in state 0 and on receives

a 0 on the input then what we want to happen is it would remain in state 0 the input would

remain at 0 and we would move one position to the right. If we were in state 0 and we

received a 1 on the input we would then go to state 13 and the input would remain at

state 1 and we would move one position to the left. If the state was in position 1 and

the input was a 0 then we would move to state 65 and we would change the input state from

0 to 1 and move the tape to the right . If in state 1 and the input was 1 we would remain

in state 1 , the input would change to a zero and we would move one to the right. If were

in state 2 and the input was a 0 then we would go into state 0 and the input would change

to a 1 we would move 1 step to the right then STOP. So this is our algorithm and it is working

on these inputs. So the contention is that this here is an algorithm in the same sense

that this here is an algorithm. The question then is we have a problem here in that we

have to be able to represent not only the inputs in terms of 0 and 1 we also have to

represent the algorithm. So what we want is the data and the algorithm to be on this tape

, so the question would be how does this machine here know whether it is acting on an instruction

or is acting on an input. So I have already drawn this out again on the next page. So

what we use is a process called CONTRACTION. So we represent 010 is defined as 1 and 00

is a 0 and 0110 is 2 and 01110 is a 3 and 011110 is a 4, so on and so forth. So let’s

see how that would work. Let’s say this is our input stream here. So this is the first

line of it there and there is the second line. Now if we were using this form of contraction

then we would know that these values here would be represented by what we have below.

So the 010 would be a 1 and the 00 would be a 0 and 00 would give another 0 and 010 would

give us a 1 and then 0110 would be 2 and 010 would be 1 and again these would be 1 a 2

and a 1 and the same for line 2 if you follow these along for example that pattern would

be 011110 which gives 4. So if we take these 2 lines and we write it in the third line

then we up with this line here . Now it’s all about interpretation and how we want to

define things. We could look at these numbers here the 1001 would be the binary number 9

, we could then define 2 as a comma because it is up to us how we define these other numbers,

the non binary numbers. So we could represent that 2 as a comma and then we would have the

number 3 and then another comma then then number 4 and then 3 and how we define 3 would

be our choice so we could call this instruction 3 and this could be anything we want for example

move left move right STOP or whatever instruction we want . We would have the number 3 and instruction

4 a 0 followed by a comma . So now we have not only the data but also the instructions

all written out in the same line so if our machine was to take this line in it would

know how to interpret it and it would read in this line here and it would act on the

data and the instructions on this line. That’s all for this little video in the next little

video we will come back and try and answer the question whether we can come up with a

master algorithm that will answer all mathematical problems. Ok thank you and goodbye.