Skip to main content
Loading Explore guides…
Counter Machines vs Turing Machines · Acedra
Home
Explore
Computer Science
Counter Machines vs Turing Machines
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
46 segments
Copy
Hide video
0:00
so we talked on the channel before about Turing machines is this Universal model of computation that can calculate basically anything that a computer can do and today I want to talk about a different model of computation my favorite model of computation which is counter machines
0:18
so should we do a bit of a recap just briefly of what a turing machine is and then we can sort of see the counter Machine by comparison our turing machine if you remember has this infinite tape divided into individual cells something like that and on that tape you can have any symbols written typically we'll go over a zero on one alphabet so we could have something one zero zero zero one one and then there is this old-fashioned tape head that moves across the tape
0:51
um reading and writing to the tape and with these instructions say if I'm in a particular state so you have some internal configuration and you can then move either to the left read or write whatever symbol is there move to the left and so on according to these instructions so that's gives us quite a lot of computing power and it was shown that you can actually compute anything that you want to compute basically with a turing machine and we've not found any computational
1:24
devices so far that can outperform a turing machine so what is a counter machine so in a counter machine we get rid of the tape completely and instead we have these individual counters which you can think of as air bags that you can't really look into and into each of those bags you can place a counter and your operations here rather than reading and writing are that you can add a counter you can subtract counter and you can check whether or not there is anything in that counter you're not
2:06
able to count beyond that you can add things in you can reach in and you can take things out and you can feel around that there is nothing in it but you're not allowed to peek inside and think oh there's 27 counters in there okay and part of the reason for that is that that is itself a computational task of you know imagine there was like three billion things in there you can't do that as an instantaneous operation so at first you see these and you think this seems like it's not a very strong
2:41
model of computation it feels like a turing machine which has this ability for you to write down anything go back read it gives you so much more power than you have from just simple moving Pebbles around between different counters what I want to hopefully show you today is that this is just as powerful as a turing machine and therefore because a chewing machine can compute anything that a modern computer can make so too can a counter machine also compute pretty much anything to
3:10
build up to that though we're going to have to start off slow and then see if we can build up to the full power of a turing machine let's start off very simply what's the Hello World of counters then the hello world of counters is okay let's say I've got and gets a few different colors here do the colors matter or is that just for you colors are just for keeping them separate no internal meaning to this let's call these C1 C2 and C3 now the simplest operation we can do is
3:42
to reset a counter so say we want to reset counter one well if our only operations are to add one counter take one counter away or check if it's empty how do I zero out counter well easy enough I take a counter away check that it's not empty take another counter away check that it's not empty take another counter away oh it's empty so we can just do this in a bit of a loop if we were to draw that the diagram might need a bit more paper so we can have our initial starting
4:17
State and then what we can say is in a loop I'm going to take my contents of my first counter and I'm going to subtract one from that and I'm going to keep doing that again and again until my C1 is empty which I'll do with a little question mark there so check every time and you kind of get stuck in this Loop until finally we are able to escape the loop because my calendar is empty and then I can leave it reminds me a little bit of a state machine diagram is it similar very much
4:49
like a state machine which I think you've also talked about before so unlike the state finite State automata there's machines without memory the labels on the edges there are about what the inputs are and when you get to 25 I put it inside a double circle which is the convention whereas here they're telling us what is the machine doing what are the operations of the machine so this is probably the simplest thing take think something away continue doing that until the counter is empty
5:18
we can build up some slightly more complex ones so if I want to add two counters together so say I want to add the contents of C1 together with the counters of C2 and let's also say where we want this to to go to as well so let's make sure we're putting into C1 that's the easiest way of working out where this is because ultimately we're going to end up destroying the contents of one of the counters when we do this so if you were to think about how would you do this if you were just playing
5:50
around with these Pebbles how would you add the contents of C2 into the count contents of C1 you would take them out and put them in it right one at a time yeah exactly so what we could do is we could subtract one from counter C2 and add one to sound C1 and then we just keep doing that one at a time and obviously checking where the C2 is empty right yep and at some point we're going to find that we run out of count as we go to do the operation again and find actually there's nothing left
6:23
in the counter and by time we've gone through that Loop we'll find that we have moved all the counters from C2 across to C1 and have essentially added those two together so pictorially we can say we're in some particular state we're going to take something from C2 add it to C1 I'm going to keep doing this until our counter C2 is empty and that's our very simple thing we can add two counters together we have in the process of this destroyed the contents of C2 so
7:01
if we need that value remaining then we're going to have to do some other operations to essentially copy that into some other temporary store before doing this operation and to copy we can again do something quite similar so if I do another one which is going to be copy let's put all of our counters C2 back and let's copy the counters from C2 and put them into C4 let's get enough of these as in advance
7:42
okay so in this case let's start in some particular State we can't count the contents of C2 and this thing oh I know I need four of these because imagine if C2 had 27 billion counters in there you can't instantaneously look and see how many do I need so whatever we're doing we're going to need to make sure that we're removing Counts from C2 and so to do that we're going to have to you know the naive approach here is well I could take one of these away add one there take one of these away add one
8:18
there take one of these away add one there and so on and all we've done here is we've moved the copy the count the contents of the counter and we've kind of lost that information we could just keep moving these backwards and forwards so if we want to do this we're going to need to be a little bit more clever and let's add one additional counter down here which I'll just call T which can be our temporary counter or C5 if you prefer and what we're going to do here is let's go with one more color
8:53
it's a good thing I've got a few different colors here okay so starting off oops with R4 here what we're going to do is subtract a red one and then we're going to add one counter to C4 which is where we want it but we're also going to add 1 into this temporary store here and so we can do that again move it a red one add a dull yellow one and a nice blue one and if we keep doing that what we find is that eventually we've kind of copied the contents here and at that point well we've got this in
9:36
this temporary store and we actually want it back in C2 so we can then do the same process that we had in the first place where we remove one add one remove one add one and we just keep doing that in a loop until our contents of C2 are restored but now we've copied the contents of C2 also into C4 so let's quickly draw out what that would look like and so when we're doing this was the first thing we did we subtracted one from our C2 we added one into our contents of C4 which is where we wanted it
10:22
and then we also added one into our temporary storage and we just kept on doing this and our exit from that original Loop was once we've emptied out the counter two so this will carry on going and we exit when C2 is empty and once we've fully finished that Loop we'll have copied the counters from C2 into both C4 and our temporary storage T but then we need to empty our temporary storage back into C2 which we can do with a simple Loop this time we subtract one from from t and we added
11:04
back into C2 and we again continue this and I'll exit from that Loop is do that until T is itself empty so we can copy things we can add things together so the next operation that we're going to master is can I double the contents of a counter let's double the contents of C1 and let's keep them in C1 so we might have to do this movement of things into a temporary storage and putting things back but the overall aim is that the contents of C1 let's start with three
11:38
there so the aim of this is at the end of this as little mini procedure we want to have six contents um encounter one in our start state what we're going to do is first of all remove a counter from C1 and this time we're going to make use of our temporary storage but rather than adding just a single counter into there we're going to add a counter and then add another counter so we can do that by saying add a counter to the temporary add a second one to the temporary
12:14
and we're going to continue doing this oops I missed my minus from C1 and so then we just continue this subtract add a counter add a counter subtract one add a counter add a counter and we continue that until we try and do it again and we say oh no C1 is empty I can't do that operation once more so after that C1 is empty and we've kind of got the desired effect here we've now got six counters but they're in the wrong place so we can do the same trick that we did before we
12:48
take one from the temporary storage and we add it back to C1 so in Reverse we take one away add one back take one away add one back and we should hopefully have six counters at the end okay so if we want to half the value of a counter what will we do well we know how to double a counter with this operation of subtracting one from one counter and adding it to another now we can do that a same setup but rather than subtract one counter from from counter one we can subtract two and
13:26
add one into the temporary storage and then subtract two and then add one to the temporary storage and when we do that we'll find that we've accumulated half of the amount that we subtracted okay question yes the odd numbers odd numbers exactly so what you'll have spotted here is that when we're doing this Loop this works perfectly fine if we've got an even number because we can make an even number of these cycles and then everything works out perfectly if we have an odd number say we're doing
13:58
three then we'll subtract one subtract one add one to T down to one then we subtract one and then we try and subtract that last remaining one we've got a problem we can't subtract we can't have negative counters I can't physically pull a glass counter from thin air so we can have another out of this point for what happens if I have a remainder of one and you can then do one of two things you can either say go back to this same position and say well modulo you
14:32
know that whatever that one remainder is we can take the quotient when we divide by two and this will work exactly the same we'll end up disregarding that one counter and have the quotient when you divide by two but if we wanted to keep hold of that remainder then we could do something by incrementing a third counter at this point we just insert something into this oh I know that I've got a remainder of one at this point what do you want me to do with it you could
15:00
store that somewhere okay so we can add things we can double numbers half the value of a counter and you can probably work out yourself if I wanted to do something like triple this or quadruple this you'd go through very much the same sequence of results but rather than just adding two counters you'd add three or five or wherever and still it seems like this is fairly rudimentary computations how can you simulate a turing machine with just moving Pebbles around with
15:27
that we're going to need to think how do I capture the information that's stored in a turing machine inside some counters
15:38
so imagine we've got this number written on our tape imagine we're using without loss of generality ones and zeros and what we're going to do is kind of split this into imagine taking a snapshot of your turing machine and splitting this into three pieces we've got everything that's to the left of the tape head we've got everything that is to the right of the tape head and we've got the thing which is where the tape head is and so what we're going to do is use our
16:08
counters to store a representation of what's stored on the tape and making use of the fact that we're using binary um ones and zeros means we can think okay well what if I take this 1 0 and think of that as a binary number one zero that would be equal to two a little suffix there to mean working in binary let's now for our second counter let's record whatever the value of the tape head is which is either going to be zero and one but we can use a designated counter for that so here we're going to
16:46
have the zero in binary which is still zero and for the right hand side we're going to flip it around so we want to try and make sure that the things that are closest to the tape head are your least significant bits and they get double as they go along so this number if we flip that around we'll have one one zero and binary which in this case is going to be six what would that look like we would have two counters in C1 and we would have six counters one two three
17:22
four five six counters in C3 and our counter for uh C2 will be empty and so what we now are going to try and work out is how do I first of all move the tape head left and right so if I were to have this as my configuration and my instruction told me move the tape head one square to the right what would that look like as changing the contents of these counters and hopefully we'll see that when we do that the operations that has on the counters are things that we've already seen that
17:58
we can do so moving the tape head one square to the right would now place it in this position and so this time this would be what the we need to put into counter one this zero is now going to be what's going to be encounter two so no change is going to be needed there and this value here is what's going to be needed in counter three so let's first look at C1 so C1 now rather than having just two counters we need one zero zero in binary which is four and some of the viewers will spot that
18:47
well all we've done there is essentially a bit shift everything's shifted over by one binary position which is effectively the same as just multiplying the counter by two and luckily what we've seen we can do already is we have a procedure that allows us to double the value of counter um from any value to whatever its double is similarly this value here was six and now we want it to go to 1 1 which is again this um bit shift by one binary place which gives us three
19:24
and again we know that we can half the value of a counter using this slightly more complicated Loop and get down from six to three very conveniently I've chosen this number here so that I don't have to worry about the awkwardness of well what if some of these numbers here are one we can work out what we need to do with that because we're storing the value of the counter in this counter here C1 so if for example this was rather than a zero this was originally a one so that would have been
20:01
a one encounter two now when we move our tablet across rather than this going to one zero zero this would now go to one zero one because we've got that original symbol underneath the tape head so rather than four we're gonna have five so somehow it's not just a case of doubling we also want to double and add the contents of whatever was stored in counter two originally and luckily for us we know how to add counters from one to another and we've got a similar situation with the right
20:38
hand side if this number here wasn't a zero but instead was a one well what we're essentially doing is this new number that we get here would be essentially the remainder would be the remainder once we divide this number by two this part here would become the quotient and this part here would be the remainder modulo 2. and those are operations that we can do with our halving mechanism we just need to make sure that depending on where we exit that first Loop if it's an even
21:15
number I don't need to do anything I just keep counter to empty whereas if I've only get halfway around that Loop then I'm going to have the remainder of one what can I do with that well I just pop that into counter two and we're done so all in all if I say I want to move to the right then for our counter C1 what we want that to be is doubled what it previously was so I double
21:51
C1 but then I also want to add our contents of C2 and in the process of doing that we don't mind destroying the contents of C2 because it's being moved it's become part of that become part we can forget about it at that point so even if it's a zero it doesn't matter anyway does it right exactly if it's a zero adding it on is not going to do anything we'd essentially be in the process of doing our addition Loop and it would just say oh I can't do the loop at all go straight to finishing
22:23
C2 that was the part where we just take the remainder of um the contents of C3 when we divide by two so in Python that is the remainder and you divide by two and for C3 well that is going to be the value of C3 I take the quotient when I divide by two so sometimes to note that with the double backslash just forget about the remainder just halve it essentially and exactly the same works symmetrically if we wanted to know how to move to the left we just essentially do this
23:01
fully symmetrically C3 we would be doubling and adding on the cap contents of C2 C2 would be the same but it would be the remainder of C1 because that's what's being pushed into that counter at that point and C1 would be the one where we are halving it and forgetting about its remainder and so with those operations we can move to the left we can move to the right we can read and write whatever the symbol is that's underneath the tape head and those are the easiest operations essentially
23:34
because if I want to write a zero well all I need to do at that point is reset whatever counter two is so if it's a zero keep it as a zero if it's a one reset it to zero so that was our very first that was our hello world of counters I just reset down to two and you can probably predict if I wanted to write one well the easiest operation the easiest way to do this is to First reset it to zero and then just add one so this can be reset C2 and then just increment it by one so
24:16
those are right operations on move operations and our read operations are really down to looking what is in our our C2 counter and it should only ever be zero or one and it should only ever be zero or one so exactly we can always just look at that and we have to be a little bit careful in the case that it's one if it's zero we've got an operation which is oh check that it's not empty if it's one we can't look and say oh I can see that that value is one we can only
24:44
do that by taking you know and trying to remove something from it and one way to do that so if I had a counter in our C2 I can't just look and say oh I can see that there's one there the only thing I can do is subtract one add it to a temporary counter just so it's stored somewhere and then I can check oh yep I know I'm not empty I must have had one there originally but you still want to have the counter there so you just do this press the remove in Reverse remove account from there and add it
25:17
back where you want it so with these simple operations you can end up simulating exactly what you would do with a turing machine so if you were to give me a turing machine program what I would do is with quite a lot of you know little mini circuits and subroutines I could recreate a counter machine that would behave exactly or analogously to how your turing machine is working and since you can compute pretty much anything you want on a turing machine then with a counter machine might take
25:50
you a few more steps and a lot of glass beads but eventually you'd be able to compute whatever you wanted to with just these that gets you there or want to and when you get to 25 I'll put it inside a double circle which is the convention because that's the finished date you've I'm going to utilize prime factorizations so the number that we're going to store into this first counter we're going to say
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat