Mathematical Games Hosted by Ed Pegg Jr. [Episode 19: Turing Machines and Turmites]

Hello, everyone. We're gonna wait until 10:30 and until the audience wraps up and I need to turn off YouTube's talking back to Me, which I forgot to do last time. And welcome. This is episode 19 of Mathematical Games, and today I'll be talking about Turing machines and termites in. In Scientific American, Martin Gardner had a column called Mathematical Games. And many of the things he talked about got further research later. And I found his columns to make math interesting a big part of my early life, and it led to me becoming a mathematician. Here is his column about Turing machines and about computers thinking, where Alan Turing had two different topics. One is what it would. What it would be like to talk to an artificial intelligence and the Turing Test. And the second part was how Turing machines worked. And there was a lot of unsolved questions about Turing machines back when he wrote this. 50 years ago. I tried out some of the discussions that Alan Turing imagined having with Turing machines, and it turned out he was surprisingly accurate. However, when I did this with gdpt, when I put in Turing's questions, I asked later whether that recognized any of the questions, and it did not, so that I found that surprising in our demonstrations project, which should be relaunched very soon. We have many Turing machine demonstrations, and I'll be showing some of them. So before that, one other thing that Martin Gardner talked about was something called Patterson's Worms, where you have a certain rule about a worm eating sediment in a. In a nutrient bed, and if it ever gets back to the starting point and there's no branches left, then the worm will die on the spot because there's. There's nowhere else it can eat. And Martin Gardner, in 1973, he showed some of the various patterns that these worms could make. And then we've got code here for doing some of these worm paths and patterns. And at the time, 1971, there were 11 worms that were unsolved. And these are sort of like Turing machines. So I wrote about these and a friend of mine, our computers, when I wrote this 20 years ago, were billion times more powerful than what Martin Gardner had access to. With the new computers, Benjamin Chapman was able to solve almost all of them. Here are some of the weird and strange patterns that, that pop up with these 11 unsolved worms. And there are still two left. And Thomas Rokiki was able to extend it. Here's. Here's one of the worms that. That pops up. However, there are still two Patterson worms left that are unsolved. These two here. So. Oh, sorry, there's one left. This one here. And it's still unknown whether or not it will terminate or not. It's believed that it doesn't, but there's no proof of that. So it's possible that sometime in the near future the Patterson worm problem will be totally solved. And a similar problem is the Busy Beaver problem. What terrain machine lasts the longest? And here's Stephen Wolfram talking about this in A New kind of science 20 years ago. These rules here, and I'll be going over these a bit more later, these roles for four states or for two, three, and four states, and for five states, it turns out that these are the Busy Beavers for the, for the various sizes. The one that was found by Heiner Markson and 1990 does turn out to be the longest lasting Turing machine, the one that writes for the longest before reaching a halting state. So there's different ways of representing a Turing machine. We just saw some, some pictorial versions. Here's some code versions. If it's in State, State 1 and Color 0, you go to State 2, you change the state, and then you go left. So here's a textual version of doing it. The last item is the state, the first item is the color, and the middle item is the direction. Steven usually prefers representing Turing machines as a rule number. So here's a number for a particular code, and this is a function for importing throwing machines in various formats. This table form is a little bit easier to read. And you can also do a table form like this. If you're given a, a given state and a given color, you get the list of behavior. And the pictorial version here, the arrow is pointing like a clock to the different states. So this one has a, basically a 12 o', clock, 4 o' clock, or 8 o' clock state. There's three different states it can make, and there's two colors. So this is showing this Turing machine's progress before it halts here. So here's a, a bit more about left, right, color and state. We start off with it in state one, color one, which is basically here. So we'll move right and we'll change to state two. Since we're in state two, we'll move left and go back to state one while writing zero. And this one is always writing the new color as one. So basically following this table and moving down when we're in state zero again and color one, so we move left again. Now we're in state two and we move in in white. So we move left again, then we're in state one, color Zero. So we move right and then we're in this state here where we halt. So that's how this table is used to progress through the two state two color busy beaver. Much more complicated with three states and three colors. And this is the sort of pattern that you wind up with. And here's the table that explains the behavior. So usually when you're running a Turing machine, you don't get the full picture. It's hard to look at say a million steps. However, if you just keep track of the, the words where the tape is writing a new element. If when it's reaching the a new furthest extent, you can get patterns which are a little bit more easier to read. So here's a compressed form of this machine here showing the places of furthest extent. Here's a piece of code to show all the various two state, two color Turing machines. This one looks rather interesting, but there's 2048 of them. Most of them are rather boring. If you change the initial condition, usually that doesn't change too much. Most of them are still boring. And with two states, two colors, they usually will end within 100 steps or at least become predictable. And here's a another demonstration we have where you can, instead of going by a rule number, you can actually change the behavior on the fly. And there's versions of this for two states, three colors, three states, two colors, three states, three colors and so on. Direct rule control for Turing machines by Shriver. Now, one thing Steven suspected was that this particular Turing machine, the 2,3 Turing machine, could be universal if given a infinite tape. And it turns out that this was true. It was proved in October 2007 by Alex Smith. This is the smallest possible universal Turing machine. However, one, one flaw in this is that it does require an infinite tape, which is sort of like programming in a way. So if you have a long enough tape, it's able to put together something which, which resembles universality. But you just don't get that right off the, right off the, at the start. So it's slightly controversial, but for the most part it does show universality. The definition of an elegant terrain machine is whether it can produce a number at the halt which no smaller tray machine can do. So here's various examples. So this is the first Turing machine which produces the number 110 and the first one that makes that particular binary number, And so on. It's an open question whether every number can be produced by a Turing machine. It's believed that that's the case, but it's still an unsolved problem. So here's the Turing machine for that number. And each of these has been given a sound file as well. Just in case you'd like to hear a whole bunch of strange Turing machines. So these are the small busy beaver. Heres we looked at this one earlier. This is the the smallest for two states or three states, two colors. Here's the next one up. So these are the, these are the busy beavers for certain small rules. And the question is what are the busy beavers beyond these? And here's some of what was known in 2011. We saw this one and this one. This is the the 42 busy Beaver and the 5 2. It stops over after 47000 steps. This is the one that was suspected for for being Busy Beaver 5 for a long time. This was the, the Busy Beaver 6 that was suspected until last year. The the biggest known three color two state busy beaver. The biggest three state three color one. And this lasts for a long time, a large number and so on. These are. These were the best known values in 2011. But most of the larger ones have since been replaced by even larger machines, some of which are incredible. And I'll be getting to those soon. So here's a start at the the two state four color busy beaver where I've just basically broken it down into a whole bunch of columns. And this one lasts for about 3 million steps or about 4 million. And as of July 15, 2024 there were 273 unresolved terrain machines. But this one here halts in a huge number of steps. 10 to the 10 to the 10 to the 3 million. So this is. This became the new champion. And here's a compressed view of what that machine looks like. Here's a Turing machine called Inverted Counter. Here's the rule here and it looks rather complicated, but when you look at the compressed form it looks rather simple. It's just basically adding on a new step every every. Well, I don't know what the, what the growth rate is, but it's basically counting very slowly. Helix has a somewhat helical looking pattern when you run it, but it in the compressed form it turns out to have a very regular appearance in the places where it's reaching its farthest extents. Here's a difficult busy beaver called Pointy Wide which has a much stranger compressed form. These were the cases that became very difficult to solve. Chaotic has a much more chaotic look. This one runs forever. But it was very difficult to prove. This one complex counter has a regular appearance in the compressed form. And one of the more complicated beavers has a very strange fractal appearance. You can see these fractal patterns all over the place here. And these are. Once you're able to prove this fractal exists, you can prove that this busy beaver will never reach a halting state. And another chaotic one here, this one looks much stranger. You've got basically snakes and strange apartments happening in the compressed pattern. And I think one more of these we have another case where you've got fractal behavior in the compressed form. And another case with very chaotic behavior similar to what you see in Rule 110 in cellular automata. You've got these gliders popping up in the compressed form. So bbchallenge.org they had all of this work done with busy beavers, but there was a whole bunch of really hard problems that were slightly beyond the, the capability of one person solving. So they basically built up a team is launched by Tristan and you. They pulled in all these various contributors and this is a, a site you can just go and take a look. So for Busy Beaver 5, here's a view of the compressed form of that. And back in May of this year, a person by the name of a username of Mixedis published the statement that the Koch proof of Busy Beaver 5 is finished. No one except the person himself knows who, who this is, but he's a person who's very good at putting together proofs, which is a. A computerized proof maker. The the next step up is probably going to be Busy Beaver 3.3. The record is this particular machine which lasts for this number of steps and it was found in 2007. Here's what the start of this busy viewver looks like, and here's what the compressed form looks like. It's not obvious that this is going to halt at this stage. You basically need many, many more steps to see that there's more chaos going on. So with these big machines, you usually need four levels of compression to figure out what's going on. And it's so far unclear how some of these techniques can be translated to something which is visually apparent. In the 33 case, there are currently 22 unresolved Turing machines left. So busy Weaver 33 will likely be solved, I'm guessing by next year. Don't hold me to it. There's. There's one case which I'll mention that is it's equivalent to the collapse conjecture. So that one probably will not be resolved, but the others likely will be here's pictures for what some of these holdouts look look like. They all seem to have strange behavior which might be infinite, but it's possible that they might stop. You can see various forms of binary counting in some of them and other patterns. So if, if you, you can look at one of these pictures and tell what's going on and prove that it's going to last forever, then you, you could join the team and basically show that you have a proof for one of these will, will never end or whether or not whether it might help. So busy Beaver 6 has this extraordinary machine. It doesn't look too spectacular at the start. You can see it has a strange compressed pattern, but it halts in 10 to the double arrow 15 sets, which means 10 to the power of 10 to the power of 10 to THE POWER OF 1015 times. And that's a really, really huge number. So it's a. It amazes me that they were able to prove that this halts because it's difficult when you're dealing with, with gigantic numbers. It's difficult to prove that something happens somewhere which is bigger than the ten to the hundred is basically the number of particles in the universe. So this number is, is so far beyond the size of the universe that it's. It's scary. But they've still managed to figure out how to make this a proof out of this. Here's one of the cases which likely will cause real Trouble. With Busy Beaver 6. You have this Collatz like behavior. If you got a 2A comma B, it goes to a 3, a B plus 2A 2 plus 1B goes to a 3A plus 1B minus 1. And the halt state is if it goes gets back to zero. It's not clear how to solve collatz like from problems. So this one here, here's the regular run and the compressed form. It's unclear whether they'll be able to come up with a proof for this one or not. And this one, Antihydra was found this year by Mixtix and Rushland. So as a counter and just in case they're not able to Prove Dizzy Beaver 6, they might want to look at termites. These are 2D Terry machines. So here's a representation for a termite I call the binary counter. It only has one state and basically you put your ant or termite on a grid, everything is blank. And basically if the state is blank, you'll turn it gray and turn right. If it's already gray, you go straight ahead and turn it white. So Basically, you always change the color you're on. And if it was blank when you entered the square, you'll turn. If you run that, what you do is you wind up running around in a. In a circle. Let me see if I can find it here. I think I'm running that one. Got a problem here. Let me rerun this. Okay, so here's a termite number four. It makes a spiral pattern. But I wanted to show the second one here. So basically, each step it's running, and you can see sort of if you look closely, that it is counting in binary as it moves around. It's sort of like the towers of Hanoi, but instead of being in base three, it's in base two. And here it finally hits 32 after 100 something steps. So this basically just keeps going around. It's. It's basically counting numbers over and over. And let's. I may have clicked the plus button too many times there. Basically, for any number you put in you. You basically get this pattern of the same binary digit repeated four times, twice reverse. However, it also has to track through everything while it's. While it's doing the counting. So it's this. Isn't this that step number? It's actually a much larger number. So binary counter is the slowest growing of the termites. Langdon's ant, which is the first one, eventually has. It has chaotic growth for a while and then makes a highway. It becomes predictable after about 12,000 steps. So one question with 2D Turing machines is not whether it halts, but whether it ever becomes predictable. The binary counter, you can basically predict it's going to count in binary. The Langdon sant is going to eventually make a highway. Other termites will have other behavior. So here's some of those behaviors. Many termites will make highways, and there's highways of various sorts. Here's a whole bunch that basically make a diagonal highway. But you can also have vertical or horizontal highways or strange wiggly highways or weird growing wedges. Other 2D term machines or termites will make spiral patterns. This one here is a very robust spiral. You've also got the golden triangle being built in larger and larger forms and various other strange tilings and patterns. But they also have a lot of chaotic behaviors. All of these are in the termites demonstration. Some of these have been. In fact, most of these on this page have been solved. What they do eventually, for example, this one eventually makes a highway. Some of these become trapped. This one, after 3 million steps, it. It gets trapped in an infinite cycle somewhere around here. So one question I asked a few years ago is, is when do these become predictable? And that became another challenge. Here's the place for it. There's nine unresolved one state, three color termites, for example. So here's one of them. After 67 million steps, a highway develops. So it's. It's really chaotic for 67,067 million steps. But then suddenly we know what it's going to do. It's predictable at that point. Here's pictures of the other nine. All of them are chaotic up to 10 billion steps. The last of these probably will resolve to predictability. It starts a binary counter at generation. What is that 10 trillion. And we can tell it's going to eventually hit this. But these binary counters are very, very slow. We can predict when it's going to hit that, but then it'll start being chaotic in eventually this one will hit some edge point and a binary counting highway will develop which won't self intersect the curve at itself again. But we have no idea when that will happen. But this one will eventually become predictable. It's unknown whether these other nine will hit a predictable state yet. So one question is, is it possible for any of these to become trapped in a cycle? Can either make highways and questions like that or is it provable that they're always just pure chaos for one state, four colors. This one resolved after 6 billion steps. And this one here resolved after 4 billion steps found by Dean Hinkerson. It has a strange double highway. One state, four colors has one of my favorite Turing machines, which I call the submarine. Here's what it looks like after 10 trillion steps. It's very slow growing, but it reminds me of a submarine. Here's the rule for it. We can get much wilder behaviors. For example, here's a Turing machine which, which has very a mix of chaotic and regular behavior. I have no idea what this one will do. Here's another one that, that develops a highway at some point, a very chaotic highway. And it's going to extend to hit this point and then go into chaos for a while. Again, it's unsolved what this blog will eventually do. And here's one that gets trapped in ternary counting within the hole. For example, when, when it ended at this number of steps here, it was doing ternary counting down here. So this is another unsolved Turing machine, a 2D Turing machine. Here's one that was resolved in two state, two colors. This is the busy beaver as it is currently known as found by Mark. After this number of Steps. It forms a highway here. This is a. The actual blob is much larger than this. Too big to show on my screen. And here's another unresolved very chaotic behavior. A lot of internal tracks and mazes are produced by this particular Turing machine. And there's such a simple appearing rule. So one question is how do these 2D Terry machines behave? I showed the binary counter. It has a nice predictable behavior unless you start it with chaos. So here's some initial condition which is slightly chaotic and it basically goes into chaos and stays there. But other chaotic starts will resolve without too much trouble. Let me see if I can find a double direction. Like for example here we basically have binary counters in two different directions. So one open question is is it possible for the binary counter to go into a chaotic state but then recover from that and go back to binary counting? That's an unsolved question. So here's some of the unsolved questions as I know them right now. What is the behavior of the last Patterson worm? There's one unsolved Patterson worm. So that would be a good project for someone to possibly tackle since it's been an unsolved question for 60 years now. Of the 24th to the 10th two color five state Turing machines, which one runs the longest before becoming predictable? We already know what the busy beaver is. So if for two color five state turn machines which have a halting state, we know now which one runs the longest before halting. However, it's still not solved. If we look at the predictability question instead, which one lasts longer before lasts longest before becoming predictable. And I'm pretty sure there's, there's a pretty good study on the 17 hardest cases for BB5. So it probably wouldn't be too hard to look at those 17 and find out the state of predictability for each of those and, and come up with that particular number and it's going to be different from the BB5 Busy Beaver. There's several that run for a long time before it. They were able to figure out their ultimate behavior but the step on which that happens wasn't determined. I'm pretty sure that's going to be a wind up being a very high number for chaotic termites. Are there initial conditions that make them predictable? That's something I'd be interested in finding out. Can the binary counter termite break out of chaos? Can any of the nine unresolved one state three color termites be resolved? We're pretty sure that that one will eventually be resolvable. The One that does binary counting, but that's not proven. The submarine termite. Does that ever resolve something predictable? I'd love to know the answer to that question. Is there a solution method for collatz like problems? Now we're getting into the really hairy realm. No one knows how to solve the collatz problem yet unless it's already been solved. It's. There's about I think a thousand or so proofs of various shape that have been put out for the collage conventure. None of them have been accepted, but it's possible one of those many proofs is actually correct. I've looked at quite a few that based on fractals which look like they have really good ideas in them, but I'm not sure any of those are really finished yet. However, due to the fact that there's so many out there, I don't think a proper survey of them has been done yet. See what is busy Beaver 3.3? There's only 22 holdouts left, but there's over 50 last year. So there's been quite a lot of Progress on both BB5 where it's now solved and for Busy Beaver 3.3 for these last two cases, the number of holdouts remaining is much lower than it was just last year. So there's quite a bit of progress on all of these happening very rapidly. So let's see. That's the talk I had planned, but I'll be glad to answer questions for a while and it looks like quite a few comments have been made here in the chat. Let's see. If you move to a state symbol combination that is not defined the machine. Okay. So yes, any questions that people have I can try to answer them. And I can try to give resources for anything that people might want to see. This by the way will be posted on community.wolfram.com sometime within the next few days and there will be a link on the YouTube page for where where the told the whole notebook is. So you'll be able to get all this code there within the next few days. Oh and I've got a question here from Twitch. Couldn't you start the I'll post it over here in YouTube as well. Couldn't you start the one state recolor Turing termite machine with binary counter at the four point where we just hit the chaotic region that is artificially extend the binary counter and then start the machine again? Yes, that's something you can try. If you avoid the chaotic region, nothing really happens and sometimes it can enter the region of chaos and then recover from it. I'm not quite sure when chaos happens, it would be good just to resolve that. At what point does the binary counter become chaotic? That would be a good question. To resolve it probably wouldn't be too hard. So, anything else? All right. Many thanks for attending my talk, and I'll be back again next month.