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.