Computational Mathematics in Undergraduate CS Education

Hi, everyone. Welcome for. Welcome. And thank you for joining us today. We'll be talking with Klaus Suttner from Carnegie Mellon University, and we'll be discussing topics related to the undergraduate education in computer science departments, how this relates to computational mathematics, mathematics education in general, and at times, computational thinking and other sorts of collections of ideas that are in this space. So thanks, everyone, for joining us. And Klaus, it's a pleasure to have you here.

Thanks for the introduction. So what I'll be talking about mostly is a course that I developed. Oh, boy. Over the last 20 years or so called CDM computation and discrete Mathematics. And I'll show you some examples of where computer algebra is used critically in the course. But before I do that, I'd like to give you a little bit of a historical background of, you know, how Carnegie Mellon in particular came to walk down this road with many perils. So what I'll do is I'll give you a little bit of a background, you know, description of the course in particular, and other elements in our curriculum that are relevant to that, and then just try to go through a number of examples, and we'll see how far we get with the example part. So I should warn you right away, from the beginning, I didn't make up a demo notebook, but I'm actually using the original notebooks that are used also in the course. So there is a bit missing here because, you know, when the student would see those. Those examples, they'd already have gone through a lecture. They'd have lots of explanations and maybe small examples written out on the board and things like that. So I'll just dump you in the middle. So if there's any question at any time, just ask. It may get a little opaque at some places. All right, so it all started a long, long, long time ago. In the late 90s. There was a couple of people here at CMU who decided that the time really was right to revolutionize the teaching of. Well, certainly of discrete mathematics. But actually we thought of mathematics as a whole. And the driving engine behind all that was thing of thought. And at the time, Andre Bauer was one of his PhD students. He was also. There was Marco Pitkovczyk. You know, you may be familiar with this book. A is equal to B. And then myself. And in. Let's see, in 1992, Dana and I, we spent a sabbatical at Bruno Buchberger's Risk Institute, the Research Institute for Symbolic Computation. And we did some experiments there. Dana taught a course in projective geometry. I did automata theory, and it Worked extremely well. It was, you know, a great success story. And so we decided we're going to do the same with introductory math and in particular the discrete math course at cmu. And so we, you know, produced a couple of courses. The first one was called Modern Math. That title was too breezy, so I should say I'm, I'm a mathematician, but my faculty appointment is in Computer science, so I'm in a slightly awkward position here. Modern Math was way too breezy for our math department, so we renamed it to Programming and Modern Math just to make clear it's, you know, computer science related. And in the end we caved and called it Mathematical Foundations of Computer Science, which is about as lame as you can make it. And these courses all were completely based on Mathematica. So, you know, the, the lecture slides, the lecture notes, recitations, everything was done in notebook format, even the exams, right? So students would come, students would come to a computer lab and, you know, work in, in a notebook to, to answer certain questions and do computations right there live. And the. So what happened was that we got, we generated a perfectly bimodal distribution. So there was a group of students who thought this was absolutely superb. It was great. They even told the friends in the math department that they should come and take this course rather than the, the traditional one. But, you know, bimodal distributions have two humps, and there was a second hump that was quite a bit larger. And those were people who were really, really unhappy about this. And I could spend way too much time trying to enumerate all the, the places where we went wrong. I just mentioned two issues that totally blindsided us because we could not imagine that it was going to be an issue at all. And so the first one that really took us by surprise was, you know, now I know it's obvious, but at the time we didn't. That our CS majors, they are extremely opinionated when it comes to programming languages. And, you know, there's the full spectrum from trying to write everything in C to, you know, using some fancy, you know, functional language like Haskell or something like that. And they simply instinctively rejected the idea of having to write code in Mathematica. Whatever. That's one of the facts that we encountered. And a little more subtle, but also quite fatal, was the complaint that what the students were asked to do in the course, in all three of these courses was to understand, learn mathematics. But at the same time we also forced them to learn Mathematica. And this really threw us for a loop completely because you know, we were thinking about giving the students this incredibly powerful tool that they could use and that would help them throughout, you know, their, their years at the, at the university. But it was perceived exactly the other way around. It was an additional burden and, you know, that burden was just unfair and shouldn't be placed on them and so on and so forth. So, yeah, in the end it really didn't work out. But so, you know, Andre and Marco both left and Dana started thinking very, very loudly about retirement. So I decided I needed to, you know, change things, change the mode of approach. And what I did in the end was to focus on upper level course rather than the introductory courses. So the, the current introductory course still has the remnants of our, you know, foundational, you know, sorry, let me just go back here. The Mathematical Foundations of cs, that's still the current name of the introductory course and it still has remnants of the structures that we built at the time. But it's sort of been drifting back towards a more traditional math course, much to my chagrin. But I'm just not going to fight that at this point. So what I did instead was to move to an upper level course and I also grudgingly returned to a more standard course format, which means, you know, there's now the, the lectures that you expected be my slides, let's say, intermixed with demonstrations in with mathematical notebooks. But you know, it looks a little bit more, and you know, the, the exams are no longer notebooks and so forth. So it drifted sort of back to the more standard format, but in the background it's all mathematical all the way. So. So, you know, the students who are not sort of fanatically opposed to working with a different computational environment, they catch on on their own and they use Mathematica to do their projects. But there are some others who will insist on writing, you know, C. And I don't care if you want to waste your time, you know, writing a C program that takes you five hours and you could do it in 15 minutes of Mathematica. It's totally up to you. So that was a bit of a shift in the face of reality, but, you know, it's been working for 20 years. So another idea that popped up at some point in my mind was that if you're trying to rock the boat and change the way mathematics is taught traditionally the first psychologically, it's a good idea to have a scapegoat that you can blame for all the misery that we currently have in our, in our math courses. And so I decided Bubhe was the right, the right scapegoat. So this is a picture of all the greats, you know, in, in French mathematics. And I think this was the first Congress in 1935. So there's Henry Carton, Andrew Donnie and so forth, all the big names. And supposedly they actually started with a problem that was also related directly to teaching. So Catal complained to Andrew Wire about not being able to teach Stokes theorem properly because there were no good textbooks. They were all wishy washy, you know, there was always an argument at some point, take a wire, make a loop out of it, send the electrical, a magnetic field to it and so forth, and that proves the theorem, which of course it doesn't. And so, you know, they wanted a, a real solid foundation for a calculus course and somehow the project got derailed. The calculus thing was never written, but they started to, you know, generate this long, long sequence of big tones that were supposed to provide a, a foundation for all of mathematics. So, you know, it starts with set theory, algebra and so on, so forth. And the project is not dead at this point, but it seems to be, you know, it seems to be on its way out. Definitely. The last volume, for example, hasn't been translated to English yet. So, you know, as far as the world at large is concerned, it doesn't even exist. So, you know, this is the sequence of topics. And what's important here to realize is that bubaki in some sense was a huge success story because it took over math education all, you know, on the whole planet. So when I went to, you know, to university in the 70s, I didn't know it at the time, but our curriculum was really completely influenced and structured by bu and this has not changed to this very date, really. The structures are still everywhere. And to my mind, that's a big detriment. It just doesn't work in the classroom at all. To be clear, these are not meant to be textbooks, right? But they're meant to build this big structure, this big sandbox in which you can play mathematics. But the basic ideas that they have, they percolate all the way down to high school mathematics where they cause damage. And so, you know, what are the problems with this bubaki approach? One of the issues that are absolutely fatal for computer science majors is that they really don't deal with logic. And it's a tragedy because, you know, this, this work started in the 1930s when modern mathematical logic really took off. But bubaki decided they didn't need any logicians on their team. So they invented their own system, which is a total catastrophe and really inappropriate. They don't care about problem solving, which of course in the computer science curriculum, right, you don't do problem solving. That's death right there. They absolutely do not care about combinatorics. So that's, you know, the swans of topology. We don't deal with that. There are no algorithms anywhere. It's nothing in any one of those books and you don't worry about applications. So there's this whole idea that the only thing that needs to be exposed is the pure abstract theory at the most abstruse level. And that's where the efforts went. They also had this incredibly insane idea really of presenting the whole work as a structure that is completely independent of external references. So don't quote anybody else. It's all bubaki, bubaki, buboki. And of course, you know, nowadays, in the days of the web and wiki and all that, that's insanity. You can't just be an isolated structure. And then the last issue that really is a complete fiasco is they don't have pictures. Pictures in their mind detract from the actual pure mathematics, which of course is complete nonsense. It's exactly other way around. It's the pictures that lead you to those abstractions. So leaving them out is just insane. So, you know, the battle cry then was, I'm going to fix this all. We're going to build a course that addresses all these issues and does a much better job at getting the message across. And so in order to have a real battle cry that would get people upset on the other side. You can see I'm constructing this imagery of two, two parts, you know, of two groups that are sort of at loggerheads with each other, which is not totally, you know, it's, it's not totally fair, but it's not totally unfair either. Anyway, so I came up with this idea to just tell the people that I think digital computation is the most important development in mathematics in the 20th century. And if you say that out loud, you know, giving a talk in a math department, things get very dicey at that moment because you're obviously, you know, intruding greatly into the territory that's sacred to the mathematicians. But I, you know, it's a provocation, it's a deliberate provocation. But I actually think it's also, it can be defended in a very reasonable manner. So, you know, 100 years from now, if people look back and what was the important breakthroughs? I think being able to Perform large scale digital computation is going to be really the big, the big issue.

And your courses. Yeah, sorry to interrupt.

My favorite computer, I had a whole lab full of those, actually. So I, I realize now that one needs to explain what this is. It's the next computer, right. It's the legendary computer that Steve Jobs built. And, you know, at the time it was decades ahead of the competition. Anyway, so, you know, the idea is computation and digital computation. The fact that you can really do it, that you can run the code, that's the big breakthrough. That's really what changes things.

Yeah.

So, you know, whenever you, you, you put out a naked provocation, it's a good idea to have a couple of very broad shoulders that you can hide behind when the arrows start flying. And so I have a couple of quotes that I can always flash up. So my, one of my favorite ones is Bill Thurston, who dispels this idea that when you use computation in a math course, you are actually effectively dumbing down the course. Right. So that's always implicit in a lot of criticism that we get. And so Thurston, you know, just said, no, no, no, no. You have to understand that what mathematicians consider to be, you know, a standard of a good, of a valid proof, that's much mushier than what the computer science people do. Getting a program to run and getting, you know, showing that the program is correct is much harder than a mathematical proof. So, of course that's fighting words, right. But Thurston can pull it off because he's a Fields medalist and he used computation a lot in, in his studies of low dimensional anthropology. So, you know, he knows where often he speaks, he understands the mathematics very deeply, but he also has an idea of what it means to write all the programs that he used in his research. So that's, that's a good starting point. And then there is Vladimirski, I should say the late Vladimirsky, who's also a Fields medalist. And he had this experience, I think it was 1990 or so when he, he wrote a paper. He was a rising star at the time with a big theorem in it. And then a couple of years later, somebody else posted a context sample on the web. And it was this really awkward situation where the counter example seemed to, it seemed to, it really contradicted the theorem. But on the other hand, no one was able to find the flaw in the truth. So it had to be wrong, but nobody could point at the place where it was wrong. And on the other hand, there was this counter example and so Robotski said, well, you know, the paper that he wrote fell into disuse. People didn't take a position one way or the other. They just didn't mention it anymore. And he became really upset about this. I mean, you know, he made a mistake. He was convinced that in fact his theory was wrong. And so he turned to, to proof assistance and theorem proving to, to verify all his work. He didn't, you know, the fact that he had this one wrong theorem was no problem because he still got the Fields Medal a couple years later. So, you know, it. But he, he took this sort of, as a, as an indication of a crisis when even, you know, the best mathematicians or the best mathematical minds cannot determine whether a proof is correct or not. We need to do something about it. And the answer, of course, is to use computation, right, to use theorem provers and, and proof assistance and the like. And he actually said, you know, a couple of years ago that he thinks that all of mathematics will ultimately go that way. Everything will be done with theorem proves and, you know, computer algebra, everything will be algorithmically supported. That may be wishful thinking, but, you know, we're certainly moving in that direction. And if you look at, you know, the computer science side of things, there's. Bruno sh is always a great, great example. So he also has this idea that you should think of, of computer science now pretty much the same way as you would think of mathematics in, let's say the 19th century, which is this, you know, this fundamental core discipline that radiates out everywhere else. So, you know, there's, there's mathematics in physics, obviously in chemistry, in any kind of science, there's mathematics. But by the same token, now it's, Computer science invades all domains. So you can take just about any, you know, any area of discourse, and then you put computational in front of it, and now you have a new field. So there is, for example, computational anthropology. So, you know, it's, it's everywhere. So, you know, all strong endorsements of doing things very, very differently from the approach that Bubaki took. And how do you actually do this in a real course? Well, it's not so clear, right. And over the years, so I've come to sort of filter out a couple of basic requirements that you have to, you have to satisfy if you want to transfer a traditional, more traditional mathematics course into something that is based on computer algebra and computation more generally. And you know, this list used to look very different years ago, but I, I'm now convinced that the, to have a document centric User interface, you know, where you can do computation and visualization and all that. It's really critical in the classroom. If you don't have that, you're dead from the start. Also, what you should have in place is some system that makes it very, very easy to, to cooperate, to, you know, to, to share information, to work jointly on projects and things like that. There needs to be somewhere underneath a really good prototyping language that allows you to translate your mathematical ideas into actual computations with very little overhead, right? So you don't want to spend time on writing complicated programs or implementing complicated algorithms in order to test out your ideas in a, you know, computational setting. So, you know, whatever system you use, it has to provide that automatically. It's also really nice. And you know, this has certainly changed greatly over the last 30 years to have a system that has, you know, a great many algorithms built in, right? And so of course, Mathematica does exactly that. You don't have to bother if you, you know, want to use a Grimma basis algorithm somewhere. It's built in, right? You don't have to waste your time by, by reinventing the wheel and writing lousy software that somebody else, you know, can do a much better job at. And you know, in contradiction to Bobaki, who doesn't like pictures, pictures are critical. So there has to be strong support for graphics. Otherwise, at least for classroom applications, it just doesn't work at all. And then the last item that's sunk to the bottom, it used to be higher up. You would really like to have a connection to a proof checker or a theorem prover. So a while ago we had our own system called Analytica. But it's turned out that maintaining, you know, a separate theorem prover is just way too much work. It's the payoff just isn't there to, to, to re. Implement the full theorem proof of in Mathematica. So typically now I just send students off to Lean. If they want to do formal proofs, go and use Lean to do that. There's equational theorem proving that's built into Mathematica, so we use that. But if it gets more complicated, then you really have to go to other sources. So you know, that was the list of requirements, the wish list, if you did, if you will. And so currently. Well, okay, so I've been doing this now, this particular course for 20 years. So I'm sitting on a, on a huge mountain of material, but a semester is still 15 weeks. And so, you know, when, whenever I teach the course, which I actually will do this for. Then I have to pick a couple of. Of topics, and I always start with computation, because that's really a sore spot. Surprisingly, you would think in a computer science curriculum it shouldn't, but it is. And in particular, what I like to do is I'd like to advise the students or guide them towards the notion that Turing machines, which are the coin of the realm, we use them everywhere, complexity theory, for example, are not really a good model of computation if you try to come to really intuitive grips with what computation means. So instead, I do register machines, and in the course, I actually show them a universal register machine. I'll show you. It'll be on the next slide. So there's a couple of lines of code, and they actually describe a universal machine. And there's a simulator that I've built, and you can run that universal machine. I'll show you in a couple of minutes. And then we move on to logic, because that's another. That's the driving force really behind much of computer science. So with slight exaggeration, you could say that theoretical computer science is just applied logic. See, so that's. First you provoke the math department by saying that digital computation is the most important development in mathematics, and then you provoke the computer scientist by saying that at least the theory part of computer science is just applied logic. So now you have, you know, both teams against you, which is actually. So I'm making a joke out of this, but this is actually a real issue when you try to. To navigate the. The reality of curriculum at a university. You need to be, you know, need to be aware of that. Anyway, so there's a bunch of logic, and then we dive down to the bottom of the computational hiring. We do finer state machines and automatic structures, you know, mathematical structures that can be described in terms of final state machines. And then in the end, there's a segment on algebra where, you know, we do group actions. And I'll show you an example. I explain how GPS actually works as an application of shift registers and finite fields, and there's lots and lots of other things, but currently this is as much as I can pack into one semester. And, you know, just to have a picture, this is a graphics I stole a long time ago from my friend Buchberger. He was making an attempt to try to explain what happens when you bring computation into the mix. And so the idea is, you start, you have some idea, you sit down, you write a little piece of code, you compute, you experiment, you generate data, sometimes lots of data. You visualize them and then hopefully after a while you're going to see some patterns. And once you've seen enough patterns, you can form a conjecture about what's actually going on there. And then the next step is to try to make that conjecture very, very concrete to formalize it. And once you have a strong formalization, then you go off and prove it in the traditional way. And hopefully whatever you've done now wasn't a total waste of time. So you've proven an interesting result and you can feed that result into the next round going around that cycle. That's why you have some, a new theorem, which will give you a new algorithm and you can use the new algorithm to do more interesting experiments. And of course, this is a gross oversimplification because it's, it's, it's not a nice circle in general. It's more zigzagging around, right. You're trying to formalize your conjecture, you realize you don't know what you're talking about, so you go back to the computation stage. So, yeah, that's, it's, it's. Yeah, so things like that, right. And you just wander off into infinity. If you go around often enough, more than a provocation.

So you would say that this is.

The question, of course, is then immediately, if you're trying to make this, you know, a course based on these ideas a real part of the curriculum, there's always the question, does it work? Right? How do the students respond? And the sad truth of the matter is that, you know, Carnegie Mellon, like any other university, is not serious at all about, about, you know, analyzing learning outcomes. We have the usual fig leaves, you have faculty course evaluations and things like that. But this is all very, very weak data. So, you know, whatever I can say that speaks in favor of the, of the success of the course. One point that I like is that there are usually a quarter to a third of the students are math majors. So what has not happened is this effect that people always worry about, about, you know, dumbing things down to the point where it's just computer science, but it's no longer mathematics. So that's, that's where they're not, not happening. The course has a reputation of being very difficult, which is fair, but still the FCEs, the course evaluations are very high. So that also means that something, something happens. And, you know, if you look at some of the student comments over the years, that's, some of them are quite amusing. I do not know how to make the mathematics of a rock interesting. I have no idea how to do that. And the martial arts reference there, that's. This makes no sense unless you know that I used to teach martial arts at Carnegie Mellon. So the students have all the undergrads of all these wild fantasies. In fact, there was once a big discussion on the bulletin board about what would happen if I ran into a math professor who has. He has a long career as a bodybuilder. If we met in a dark alley in the middle of the night, they had all these theories about how it would work out. The reality is, of course, we would have gone to the nearest watering hole and had a beer together. But anyway, so it's. From whatever vague data I have, it seems to be working pretty well. So that's the. The background, right? It's the idea of. Of trying to really get serious about the fact that we live in. In a totally different world now in many ways than we did. You know, even, you could say throughout the 20th century, we have all these new tools around lying around. And to my mind, it's perfectly clear that we're not beginning to make real use of them. You know, they can be pushed much, much further. So, you know, whatever I've said, this is all about discrete math. You could make exact the same arguments about, you know, a course in calculus or differential equations or things like that. Yeah, yeah. The details shift quite a bit, but the basic ideas would be completely compelling. The same. So I mentioned already. Oh, boy. You know, one of the issues that I'm unhappy about in our computational thinking curriculum is that we follow the traditional lines of defining computability, which means we talk about Turing machines over and over and over again. And the justification for that is that in the end, when you look at the point where computation really pushes down hard on computer scientists, I mean, they have to take a course in complexity theory that's completely based on Turing machines. And so you want to explain everything in terms of Turing machines. So they get used to the idea of organizing computation with these little devices. And it's. I understand the reason why we're doing it, and I think it's still a great disservice. You can do much, much better by using a model that's much more intuitive, and in particular, intuitive to computer science majors. Namely, you construct a. A very primitive assembly language, and then you express all computation in terms of disassembly language. And so, you know, formally, these devices are called register machines, and the language they use is completely trivial. So you think of having a bunch of registers that can contain natural numbers. So you know, 0, 1, 2, 3, and so forth, and the number of registers fixed. And now the only operations you can perform in this very, very weak language is you can take the contents of a register and increment it. And then when you're done with that, you continue execution of the program in line K. So this inc SK means increment register number S, and then continue execution of the program in line K. So add one and then there's a second instruction, decrement rkl. So this is a conditional thing. Oops. This should be an S. I'm sorry. If you look very carefully, what looks like an R here on the screen is actually an S. Can you morph it automatically? So you look at the register, you check whether it's currently positive or not. If it is, you decrement it, and if not, you do nothing, because we only use natural numbers here. And depending on whether the thing was zero or not, you continue execution in line K or you continue execution in line N. So that's the second instruction, and then the last one is halt. And so the big advantage of this is that anyone can immediately understand, certainly every CS major can immediately understand how these programs work, right? You can just increment, you can decrement, you can stop. That's it. Nothing else. So it's extremely straightforward. And it also gets you around coding issues because you don't have to worry about how you express the input on the tape of a Turing machine. Everything is just a natural number, right? So you can do addition, multiplication, you know, you can go through the whole panoply of basic number theory functions, and you can implement them with register machines. And that's. It's very intuitive and it's. The. The cognitive burden is very, very small. And so one very nice feature of the, of the register machine approach, as opposed to Turing machines, is that you can actually explicitly write down machines that do something interesting. So, for example, here's a. A flow chart for a register machine that takes as input some number X and then figures out, if you write that number X in binary, how many ones are in the binary expansion. So I don't want to go through the, you know, you can.

Yeah, as I understand you, instructions, right?

So one of them is the halt instruction. This is where everything ends. And other than that, you have only incremental decrement. Well, if you do an increment operation, there's only one thing you can do, and then you continue somewhere else in the program. So this is a node without degree one. But if you do A decrement operation like this guy here. Well, there are two possibilities. Either the register was already zero, in which case you do one thing, maybe you go over here, or if it was positive, you do something else and you go down here, right? So you have a very simple diagram where every node has out degree, either one or two, depending on whether it was increment or decrement. And then there's one place where there is no, no out edges. And I mean the whole thing state. But it's totally straightforward.

So as I understand, you also have.

Already a mess because, you know, organizing counting functions is not so easy to do. But here it's very simple and you can, you can visualize how the machine works. I'll show you in a second. And so, you know, the ultimate challenge always is when you have a computational model is to, to show that there's a universal machine, a machine that can simulate all the other machines. And with register, with Turing machines, this is a nightmare because universal Turing machines are extremely complicated. And you know, even Turing himself made a mistake in his famous paper. The machine that he first wrote down wasn't quite right. It was not hard to fix, but it was wrong. And so here's a little 13 line, well actually 14 if you count zero. A little register machine that can simulate any other register machine. But in order to be able to fit this so nicely on one slide, I'm cheating quite systematically. I have added a few instructions, macros really, that aren't in the language. There's a copy instruction, there's a write instruction, a read instruction, pop and so forth. These are not there, these are higher level constructs. But it's very easy to verify that this copy instruction could be rewritten as a small register machine where you really use the actual language. And you know, on the right hand side, there's an explanation of how this thing actually works. And you know, this produces a whole bunch of very wholesome projects that the students can work on. For example, you have to show, or, you know, a reasonable challenge is to show that this allegedly universal machine here really is universal. Prove it. And that requires, you know, quite a bit of argument and reasoning. And it's, it's a very good exercise. The machine that I've just showed you is really not a register machine. It's a register machine with macros. Okay, rewrite it so there are no macros. Take them all out. So expand all the macros into little snippets of code that do the same task. So you get really a register machine, plain Register machine and try to do this in the most economical fashion. So make the register machine small, try to really push it down to the, to the limit there. And then, you know, there's all kinds of other things. So for example, you could ask somebody, you know, this may seem like an insane question to, to write a simulator for register machines. Well, you know, it's obvious how to do this, right? You just ex. It's a small assembly language. You just execute the instructions. But actually if you look at one of these diagrams here, for example, if you go on the right hand side, so here is one particular instruction that says decrement Y. And if Y was not zero, then the next thing you do is you increment X and then you do the Y ox, the Y obstruction, the Y instruction again until you finally have Y equals zero, and then you go off to the other side. Well, you know, what's really happening is here is you're emptying out Y and you're adding Y to X effectively. So this is really an instruction that could be written more and more, you know, more concisely as X is equal to X plus Y. Write a program that figures that out and then replaces this loop by a single instruction. And then keep on doing it until you have a simulation that takes all possible shortcuts, or at least all possible shortcut is asking for a lot, but at least some of those possible shortcuts. And so you can actually simulate those machines for trillions of steps. Because you're not running through the trillions of steps. You have a clever way of abbreviating things and then, you know, things are attributable. So there was one student a couple of years ago who did a fantastic job at writing a fast simulator. It's like simulating the game of life, right? Anyone can write a simulator for Game of Life. But if you want to have a simulator that really works well with, you know, gazillions of points and over gazillions of steps, then it's real work. Same here. And you know, the, the core audience audience is computer science majors. So it's perfectly fine to ask them to write a compiler, for example, that translates a Turing machine into a register machine. The register machine simulates the Turing machine. And you can experiment with busy beavers and things like that.

So these are examples of what kinds of projects.

This approach will provide a better intuitive grasp of what computation really is in the formal sense where you, you know, you can sort of see at an intuitive level how things work as opposed to being in the world of Turing machines, where everything looks to be very primitive from a distance, but then when you actually go down into the nitty gritty and you try to really prove results, it turns out to be really complicated. So, you know, in the, in the, in the complexity theory course, for example, there's the standard mantra, there's this invocation that says you can construct the Turing machine that does this and that, but you never do it. You never actually construct the Turing machine. You only talk about them. And so here, this is the remedy. We actually built these machines and we can mess around with them. So there's this simulator for register machines that, you know, runs in Mathematica, of course, and I want to just show you one example. So this is. Sorry, this is not dressed up very nicely. You know, you all know the, the famous Collatz function, the 3x +1 function, where you start with a positive natural number. If it's odd, you multiply by three and add one. And if it's even, you just divide by two. And then the claim is, if you keep on doing this long enough, no matter where you start, you always wind up at one, right? So by just applying this 3x +1 function over and over again, ultimately you'll get to one. And so there's many different ways you can translate this into a register machine. I'm just going to use this one here. And so this is really a register machine. No flaky macros. There's only decrement and increment operations that in the end, down here, it holds. And this thing computes the 3x +1 function, and in a loop, it keeps going until it hits one. And so there's this simulator that runs the program, and, you know, it's a trace of a computation. So what do you expect? Well, you get gibberish, right? You get a data dump that tells you this is what happened during the computation. But, you know, in this environment, it's really, really easy to filter out the relevant information, namely, what happens whenever the machine is in state zero. So this is what I'm doing here, is I'm filtering out the steps during the computation where the machine is in, you know, in the first line of the program. And then you, you look at the register content and guess what, right? So initially the input was three, and then it goes through a bunch of steps, and then the, the, the register changes to 10. Well, three times three plus one is 10, right? And then you divide by two, you get a five, and then 16 ends on so forth, right? So the, the, the point here is that now that you have the whole computation, the whole trace as a simple data structure, you can start mocking around with it. And particularly you can try to visualize what these computations look like. And there's many different ways you can go depending on what you're interested in. So, you know, here's one plot that's perhaps a little, a little more appealing where you try to understand how two registers hang together. You know, in this particular case, there's, I forget which is which one is the X register, the other one is the Y register, and you really can see how the computation unfolds. So, you know, you can ask all kinds of questions, what these pictures would look like for a particular computation, and then really the place where things become more or less inaccessible. In a different model, you can make up a register machine, a universal machine that simulates all others if you allow yourself to cheat a little bit and use macros. But, you know, then the students, as a homework, have to get rid of the macros. And so here's. Let me just use one of those. There's one universal machine that doesn't expect memory to be zeroed out. So this is the macro version, right? This is the one that I showed you on the slide. So it's a total cheat because I pretend I have all kinds of operations that aren't really there, right? But, you know, you can easily enough simulate them. And now, you know, you can really, at a very tangible level, verify that this machine works by taking a small program, a registered machine, and then running it, right? So here is a completely idiotic program which just adds one to a register. And the reason I'm using the really small one is because in order to provide that register machine to my universal machine, I have to code it up as an integer. And in this case, the code number is 160. And by the way, in the course, there's a long explanation how to, how to implement these coding functions. So these are basically good old numbers, but in a civilized way, you know, the, the machinery that Griddle invented is exactly the same. And then you can do fantastic things like checking with our universal machine here that 11 plus 1 really is 12, right? So you know, what you really need to do there is, of course, then go into the, in looking at the trace more, more carefully and see how the universal machine really has gone through a bunch of steps. And this is not, I'm not cheating. How about 17? Output is 18. So this is what I think of as a correctness proof. We now know for a fact that the machine works and the simulator works. But, you know, so I'm only kidding. Halfway to, to really give correctness proofs is, Is a excellent exercise and it's quite difficult. You have to do all kinds of inductions. And, you know, it's, it's very nice for the students to be able to actually get their hands on these devices. They're not just some abstruse concept that floats around somewhere, but you can actually build them and you can work with them. So that's the, the, you know, the initial part where since the whole course is supposed to be about computation, we actually give a civilized definition of computation. And then, you know, you apply from there on in other parts. And so, you know, in, in a sense, this is the abstract theory of computation, but made fairly concrete as far as you can make it concrete. Now the next step is going to be to actually, you know, go all the way down into the weeds and do computations that are really, really concrete, efficient, and, you know, fast to execute. And so the way it's organized in the courses, I talk about finer state machines for a while. So, you know, final state machines are one of the big success stories in computer science because they just, they are the right conceptual tool to describes or describe all kinds of, of systems. Like, you know, your, your Coke vending machine is the inevitable example or tools in Unix like Grappler, so where you search for patterns in, in, in. In files and things like that. So this is eminently practical. And the way it's organized, again, is to try to push the students into an understanding that at least a big part of discrete mathematics directly translates into a bunch of corresponding algorithms. And the algorithms then, you know, can be used to explain discrete mathematics. Right? So, you know, a finite state machine is a really simple model of computation. Everything you can imagine, you can actually implement with finite state machines. And then once you have those, those, those algorithms implemented, you can use those to study the machines in greater detail. Right? So there's this, There's. There really is a feedback loop where the results of your previous ideas produce new algorithms and the algorithms that help you to come up with, you know, a deeper understanding and more complicated ideas. And so. Oh, boy.

Yeah.

Let me just continue with the slides here. So one of the, the issues that one finds typically butchered in a lot of approaches to final state machines is the issue of minimization, right? So it's, it's a, it's a, you know, big theorem that says if you have a very simple finite State machine, the so called dfa, a machine that's deterministic and has a unique initial state. Then you can minimize them, you can eliminate useless states and make the machine as small as ever possible. Right? And there's an algorithm to do that. So if somebody gives you an inflated machine, you can ship it into the algorithm and what comes out is then the optimum machine, you know, that solves a particular problem. And the way it's handled traditionally of course is you just talk about equivalence relations and then you talk a little bit about how to compute an equivalent relations and that's it, right. So what we do instead is, oh, just to give you an example, this is half a page taken from the Bubaki sets volume where they define essentially equivalent solutions. But you can just look at the image, you don't even have to bother to read it. Just, you know, relax, go into a state of no mind, look at it and you will immediately hate it because it's, the way that the information is presented is just really, really difficult to, to absorb, right? It's very hard to read. Now I will admit that this is not what you find in a typical discrete math textbook, but it's not that much different either. You know, this is exactly the definitions that you will found in the standard book. And it's just hard to wrap your head around this stuff. And so what we do is we, we actually sort of fully embrace the, the abstract part of equivalent solutions first, but then we drill down into some concrete algorithms that are based on that. So for example, the first step is to say, you know, if you'd like to compute with an equivalent solution, you can translate that problem into something that's much more amenable to, you know, a computer science approach to an algorithmic computer function instead. So you have some equivalence relation and in order to describe that equivalent solution, you find the right function so that two elements X and Y are equivalent if and only if that function X, that function agrees on X and Y. So if F of X is F of Y, then X and Y are declared equivalent, otherwise they're not right? So if you give me a function from any domain A into any domain B, then I can always use this to produce an equivalence relation on A. Because you know, two guys are equivalent if they have the same value under the function. So that's something that's obviously you can do very easily in the program and it's easy to check. It doesn't matter what the function is, you always get an equivalence relation. What's a little Bit harder to realize is that every equivalence relation looks like this. So if somebody gives you an arbitrary equivalent relation, you can always represent it as a function. And the simple way of doing this is completely useless computationally. That's why it's interesting for us. So you can just map X, an element X to the equivalence class of X. Then two guys are equivalent if and all of the same image. And that's completely useless from a computational perspective because you start with a perhaps simple set A, and then you map into the power set of A. The power set is a computational nightmare. You can't really do this. So that doesn't work. And then the inside is, you don't have to do something complicated. You don't have to go into a difficult set B. You can just replace B by a. You can choose a function that maps elements of A to elements of A and that describes the equivalent solution. And interestingly, if you want to do this in general, the way you do it in math, that requires the axiom of choice. But of course, for us, we don't care about, you know, abstruse sets that have no real tangible description. For us, really, the objects that we ultimately mostly interested in algorithm, just natural numbers. So this is a slight exaggeration, but not much really. We can always enumerate things, right? And so in some sense you can think of whatever you, you, the objects already dealing with. Well, they're just numbers 1, 2, 3 up to n, right? That's pushing it a little bit, but it's true, right? You, you can keep a table somewhere that tells you what the number five actually really represents. Or it's, it's, it's essentially you're just dealing with integers. And now once you have that idea and the fact that you can represent the equivalence relation as a function from bracket m to bracket n. Well, now you're just talking about an array. It's a plain old fashioned array where you, for every, for every I less than or equal to N, you have a particular object X sub I, and it's all natural numbers. It's trivial to implement. And so if you, if you're willing to, to buy this, this assertion that without loss of generality, I can think of everything I have to deal with as just natural numbers. Now that means every equivalence relation is just an array, an integer array. And so now, of course, you can compute with that, right? And the computation is very straightforward. You know, what's the, what's the, you know, obvious idea if you're supposed to pick one particular element in the equivalence class that is supposed to represent the whole class. Well, it's just numbers. Everybody will do the same. You'll just pick the smallest element, you'll pick the min, right? So if you have a bunch of guy numbers, 1 through 100, and some of them are equivalent for each equivalence class, just pick the smallest element in the equivalence class and that's what represents the class. And since you can represent everything with integer arrays, that's straightforward to do. You can then calculate with these equivalence classes. And this task of minimizing a final state machine is easily seen to be manageable in quadratic time. You have an algorithm that runs in up to N rounds, where N is the number of states of your machine, and each round takes n steps, essentially linear. And so the total damage is at most N squared, though actually in reality, often the number of rounds is much smaller, smaller. And so you get a pretty reasonable algorithm to minimize my state machines by basically just following through with this idea that the axiom of choice translates equivalence relations into functions and in a very concrete way, right? So some people object at that point that it's insanity to say the axiom of choice is somewhere all, when all you need is a minimum of natural numbers. But you know, that's really where it comes from. And so you get this connection between relatively abstract mathematical concepts and concrete algorithmic implementations.

So we've seen two examples here.

Once you have this idea that an equivalence relation should be a function on the set that you're interested in, now you can immediately tweak this a little bit. So in the original formulation, we say X is equivalent to Y if F of X is equal to F of Y, right? So that's the, that's the, the most natural way of doing it. But now you could back off a little bit and say that instead of insisting that F has the same value on X as on Y, think about following the orbit of X on the F. So you compute F of X, then F of F of X, then F of F of F of X, for you apply F over and over again. And now if you set things up the right way, when you do, when you apply F over and over again, after a number of steps, you'll reach a fixed point. So this doesn't work for all functions, but for the ones that we're dealing with here, that works fine. And now you can get a new kind of equivalence by saying that I don't really want, I don't insist that F of X is F of Y. I'm already happy if the fixed point that I get to from X on the F is the same as the fixed point I get to if I start my computation at Y. So this is a weaker condition, right? It just says you have to apply F a couple of times before you finally get stuck somewhere. And that's what tells me whether the, the original starting points were equivalent. And guess what? This is just the union find data structure. It's, you know, it's exactly what's being done to represent unions of disjoint sets. That's, that's how you, how you do it. And it flows very naturally from this original representation of equivalence relations as, as, as integer arrays, right? This is just repeated table lookup in the integer array. That's all it comes down to. And you know, if you, if you, in the context of finite state machines, this will give you an algorithm that is log linear to check whether two machines are equivalent, whether they accept exactly the same input. And of course, you know, you can plot pictures, right? So here is a, a very simple minded way of, of, of representing an equivalence relation by just doing it in the most ham fisted way. And what you get here is a structure that looks like this. And now the problem here is that if you start at. Let's see what I cannot. Can you see my cursor? Probably not. Right, let's say you start at the very highest point up there in the middle, right? And you would like to know whether this is equivalent to the point all the way over here on the left. Well now you have to apply the function not just once, but you have to apply it repeatedly. And you can see that there could be a pretty long chain of steps that you have to take until you finally can come to the bottom here. Found the root of this complicated tree on the left, so it's a little bit slow, at least for a lot of the points. And now there's this trick of speeding things up, which, it's a programming trick, we don't have to worry about it. Your path compression and ranking. And now when you use that additional trick, then the picture I just showed you turns into a totally different one where the tree gets incredibly shallow. It's just let's say 1, 2, 3, it has level 4. So in the worst case you want to check whether two guys are equivalent, you just have to evaluate that. You have to do four table lookups. And so this is almost as good as just doing one table lookup so you can do things very, very efficiently.

We are actually nearing the, the end of what we're going to have of.

Firestate machines, of deterministic firestick machines really should be testing so we'll implement it, of course. Let's see. Oh boy.

Yeah. Can you. Can you hear me?

Random topic.

I was just going to say we're nearing the end of what we have time for the stream.

Let me just. Sorry if you said something, I didn't hear you.

Yes, I was just going to say we're nearing the end of what we have time for the stream. But you know, I know that we.

Have a lot of things not right. That seems to be good.

Can you hear me?

I cannot hear you anymore.

Ah, yeah, we suspected some audio issues on your end possibly. So if you can't hear us. Well, we're near the end of what we have time for in terms of our scheduled time, but we will definitely, as we have to cut out here pretty soon, we will schedule a time when we can go through more of these examples because we actually have a lot more follow up questions about. You showed many examples about how the. That spiral of creativity as you're talking about where as you're going through these computational examples, bringing an actual computer to the mix really helps bring these abstract concepts to very concrete things. So we suspected there was a little bit of an audio issue here as we had some audience questions that we would like to bring in. But again we will get those sorted and we will have to have you back on so that we can go through more of these examples and get to more questions that we have on this topic.

Okay, so now I can hear. Again, I'm sorry, I was. For some reason my Jabra speaker went off so I have no idea what he said in the last two minutes.

Can you hear us now?

I can hear you very clearly, yeah.

Okay, so we were just saying that as we're nearing the end of what we have time scheduled, we're going to definitely have to bring you back for more of these examples. We suspected there was an audio issue on your end. There were a couple of questions that we would like to get to. But yeah, so we'll definitely have you back and we can go through more of these examples and sort of really drill down onto how does the computation that students are creating by working and modifying these pieces of code relate to these abstract ideas and what in your experience shows that this is a better approach as compared with sort of a traditional discrete math. But again, thank you so much for joining us and unfortunately we do have a hard stop as we're getting ready to start another stream coming up, but we will definitely schedule a time where you can come back, and we will go through more of these examples. And this is really great stuff so far, and we're really.

Okay, I've lost you again. This is very strange.