Busy Beaver Turing Machines - Computerphile

the video that I want to do today is a direct followup of the one I did a few weeks ago which Shan somewhat misguidedly entitled the most difficult program to compute question mark it was of course all about the aan function today I want to show to you the busy beaver problem or the Busy Beaver game and it is far worse than aaman it was invented by a gentleman called Tibor R in 196 2 what he in his later years took on was to teach beginners about touring machines now many of you on the Sha and Brady wish list of topics to be covered that I want to know about touring machines I want to know about undecidability so this is a lovely uh way to pull it all in because this thing this program that behaves even worse than aiman depends and is utterly Rel related to the idea of a touring machine for those of you who want just a bit more detail about what's going on at the touring Machine level and exactly how torado developed a particular form of touring machine suitable for this game then I'm going to refer you to this short introductory movie so let's look at the particular formulation of a touring machine that tior formulated as a game which you can play with your computer program and in fact there's web pages devoted to this you can join in on the Busy Beaver community and see if you can find a beaver that's even busier than the ones currently known but be warned as you want to go up and up and up in size of this problem it goes up worse than super exponentially this is the single state tuing machine for the Busy Beaver problem what the heck is this busy beaver problem busy beaver asks what is the maximum number of Wands that get printed on your tape for your given touring machine when it hals now I've got to add that to the end because as we discover there are some there are lots of Rogue touring machines which will go berserk either printing endless ones or even overwriting them with endless zeros and going either to the right or to the left so this well- behaved ones we want them to Halt and stop and just leave a big big tape with lots of ones and zeros on it and it's called Busy Beaver because this program is just going bananas walking up and down the tape writing ones and zeros seemingly arbitrarily but in accordance with the program instructions on the cards and you're just saying how many ones do I end up with what's the best or worst I can do well I think this will become a bit more alive to you now if we take a real actual example of a single card touring machine for a busy beaver so we stick our read right head in the middle of this tape to start off with there it is and this is card one it is the only card available to because this is a one card touring machine rule is your start card is always card one the first thing you say is read a symbol so you read a zero okay what does the instruction card tell me to do it says over write it with a one that's the overwritten one zero remember means move to the left that next zero so you move the head to here one that means go back to instruction card one I'm already in instruction one so what I do is go back in there like that but now again you say read what's under the head well the head's moved to here but you're under another zero now so you say okay overwrite that zero with a one shift to the left cuz that's what the zero means oh BL me move the head here go back to State one we're already in state one go back and do it again you can see straight away what's going to happen here I'm going to whiz off to the left writing ones and it will never never stop so here's the first example then of what I referred to in the previous video I told you there were things called recursively innumerable programs that sometimes stopped and sometimes just whizzed into loops and went on forever well here's a nice simple example of it given that right at the start youve probably don't know whether your given program is going to wiiz it left or right or whether it's just going to mess about in the middle start it in the middle give it enough space to go left enough space to go right but the rules say in principle if it needs infinite tape give it enough now a lot of the art of this kind of programming is to say Arbiters it looping it's pointless giving it infinite tape if it's just going to Loop and loop and loop and not do any different thing forever and yeah very very clearly this one's looping so we've done a one card touring machine Busy Beaver attempt here and just seeing how easy it is to get into a loop and spin off doing zillions of ones that will never end and you might say oh that's the idea then is it a sort of infinite Busy Beaver it just spews out ones forever and unfortunately the rules of the game say that doesn't count it's got to Halt there's got to be a finite number of ones that you can count ones that just go on forever don't count so you need to get into a halt State somehow or another and uh have a finite number of ones to count up so let's do one that is still a single card candidate for a busy beaver touring machine but one that doesn't Loop indefinitely this time I'm going to make it be zero if I read a zero then I my actions are one one Z actually some of you will have spotted already that in a one card setup like this given that you move the head off to the left or the right all you ever encounter is zeros you are not going to get into a state of ever reading a one because you you only got one instruction and you either keep re obeying it as we saw last time when you loop back into itself or it's a oneoff thing and it does one thing and stops and in this particular case well I'll put one one Z here for the one case we won't need that because look what happens if I've read a zero which I have there what do I then do the answer is I overwrite it with a one the next one to the right of that in the instruction layout says shift right remember a zero at that position is shift left this one is shift right so I shift the readwrite head to the right but then c0 is the halt State wow bound to win an award it reads a zero it overwrites it with a one it shifts one place to the right and then stops wonderful extremes isn't it it either whizzes off and never stops writing ones or else it does precisely one one and then stops and says done it let's just do a bit of mental arithmetic here it's not too difficult in this case you've got zero or one as the things you might be reading but here you've got a triple of binary digits you see either n or one that you read it's either n or one that you shift left or right and it's either the halt state or back into one which is where you go right so Sean you start off at 10 2 to the^ 3 is eight you've got that in the zero case and in general you've also got to say well I've got eight possibilities for the one case so 8 * 8 is 64 there are 64 one card touring machines but there's only about four possible behaviors you either zoom off to the left Printing and overwriting the cells with either ones or with zeros or you can write one shift to the left and stop one shift to the right and stop or overwrite a zero with a zero shift to the left and stop or shift to the right and stop not exactly thrilling but since the aim of the Busy Beaver game is how many ones can you write regardless of which of the 64 cards you choose and you must try them all out the answer is you never get better than one you write one one R in his paper calls the score Sigma Greek Sigma the score for a one card Busy Beaver the best you can do is one remember these touring machines are just made up of sets of cards in order that's all so for the order two you're going to have a C1 and a C2 if you're having a C2 possibility a two card thing then that fin final column could be not to Halt it one to go back into yourself or two to go to the other card so you've got three possibilities in that final column now so it's not like 2 * 2 * 2 it's 2 * 2 * 3 anyway you work it all out for the two card case would you believe there are 2,736 touring machines so how many 20 3,736 this number which is just how many touring machines have you got to look at to see which behaves the best in printing out lots of ones this only goes up exponentially this number this isn't bad but each one of those machines can behave worse than super exponentially so R's number for how many touring machines you can see it in this paper I leave you to work out for yourself why this is true the number of touring machines let's call it n of n is 4 * n + 1 all raised to the power of 2 N let's see if that works if I put in one here for n right 1 + 1 is 2 2 four 8 8 to the^ of 2 * 1 2 * 1 is 2 8^ 2 64 right what about if I put in N is 2 2 + 1 is 3 3 * 4 is 12 12 to the power of 4 12 to^ of 4 is 2 , 736 so your first job is to enumerate all those chery machines just get all those possible two card combinations that make 20,733 different possibilities and you can start to weed out the rubbish straight away you can clearly say first of all if your chosen machine doesn't have a halt State somewhere in it then it's never ever going to stop and it can't be a contender so you can rule out all the ones that don't have a zero somewhere in a right hand column you can soon get rid of those that cut it down a little bit but then you have to start running the touring machines to see like I've done here do they halt if they halt How many ones have they written by the time they've halted it tends to be the case that all the ones that get written pretty well Bunch together but the rules of the game saying that's not absolutely essential just start at the far left with the earliest one read across to the right and count at the number of ones you've got and that's your score but it must halt it mustn't be in part of a I'm going on forever sort of loop there are some candidates for best Busy Beaver of the two card touring machine what's the maximum number of ones that they can print out four not very good and think what's all the fuss about when you get on to three card touring machines how many of these are they're on your short list 16,777,216 three card touring machines what's the best score you can get off a three card machine still only six doesn't look very ominous or Dreadful at this stage four card ones how many of those are there now I've gone up to about four card ones in the program I'll give you the answer is 25.6 trillion possible touring machines all all of which have to be run and their behavior investigated or they have to be eliminated these are four card machines what's the best score you can get off throws 13 and this goes worse than aaman yeah this is the false Dawn it just goes berserk now when you come on Five Card Busy Beavers which is where there huge research still going on the best score so far off a five card tring machine and I've not worked out how many of those there are it's going to be huge all of which have to be investigated the best score for a five card so far is 4,098 it's coming up to 25 years ago that that number was discovered 4,098 is the best yet so I hear you say what are they messing about at about 25 years and all right there's a few trillion quadrillion Ching machines to be investigated but all the obvious rubbish would have been weeded out by now I may say that the uh German uh researchers who discovered this number did have access to a supercomputer it does help what's gone wrong why isn't there a better result and if you look on the Wikipedia page for this you'll find the answer the answer is that there are 40 candidates still running which might produce an even better answer than 4,098 and you'll say but surely the darn things are either discernably looping or else they've stopped no it's really horrible this is a nasty part of it you can get touring machines where you can't tell whether they're looping or not they consume a lot of tape and then they come back and they overright bits of the tape and you know and you think have I seen that pattern before in the case that I did for the one state TR machine when it's going one one1 one11 over it takes no genius to say it's looping and it's doing nothing with producing wands but you can imagine that as the numbers go up you could get very very long cyclic periodicity with a periodicity of 20 million or something like this T borado and his student were the people who worked out that for a four car machine 13 was the best result you could get but in getting that result they still had to look at a handful of Rogue machines they weren't sure whether they stopped or not some of them they could prove programmatically were definitely looping others they could use human inference to argue yes that is looping and I can show you why so yeah 13 is definitely correct but for the five case who knows join the Busy Beaver Club get your own supercomputer do the work and somebody out there has gone on to order six and it is reckoned that the minimum possible score for an order six Busy Beaver will be of the order 10 to the power of 10,500 now that's getting very close in size to acan 42 you know at two to the power of 60 something thousand nobody knows what the right score is so can you see that already by order five or six you're getting into acan siiz numbers and one of the things shown on the Wikipedia page which will Delight you is that for all sufficient n and n is not very big Busy Beaver numbers will always outrank aaman numbers and the reason for that is that again in the literature which you can look up for yourself the reason is that the Busy Beaver can be shown to grow faster than any computable function it doesn't matter what you put in there but if it's a computable function that has an answer Busy Beaver can be shown to grow faster than that in the long run it may not do for for small then but eventually it'll overtake it and go completely mad so yes the answer to the horrible question is are you telling me this thing gives you even bigger numbers than acan does yes it does effortlessly bigger some people say I don't believe all this stuff about recursively innumerable sometimes it can you know sometimes this machine can stop and give you an answer and sometimes it just whizzes around forever well here you've got it in front of you um and really it is not terrifically useful except it's here as a teaching example of saying it may seem pointless but this is the worst that can happen with a computer program you set on the face of it what seems to be a perfectly straightforward thing run this touring machine hope it halts and then tell me how many ones it prints out but behind that is a huge ug GE amount of illustration of theory you think oh that's going to be no worse than super exponential even when it explodes and takes off this one Rockets up far faster than aaman and very often you will say if problems are badly behaved they are either super exponential or they may be even worse they may actually be undecidable and this is what you are saying in this thing here

Channel: Computerphile

Views: 399,390

Keywords: computers, computerphile, computer, computer science, busy beaver, turing, turing machine, tibor rado, professor david brailsford, university of nottingham, Alan Turing (Computer Scientist)

Id: CE8UhcyJS0I

Length: 17min 56sec (1076 seconds)

Published: Tue Sep 02 2014