Embedded - 474: It's All Chaos and Horror

Episode Date: April 5, 2024

Logic gates and origami? Professor Inna Zakharevich joined us to talk about Turing complete origami crease patterns.  We started talking about Turing completeness which led to a Conway’s Game of Life-like 2D cellular automaton called Rule 110 (Wikipedia) which can be implemented with logic gates (AND, OR, NOT). These logic gates can be implemented as creases in paper (with the direction of the crease indicating 0 or 1).  The paper describing the proof is called Flat Origami is Turing Complete (arxiv and PDF). Quanta Magazine has a summary article: How to Build an Origami Computer. Inna’s page at Cornell University also has the crease patterns for the logic gates (pdf). Inna is an aficionado of the origami work by Satoshi Kamiya who creates complex and lifelike patterns.  Some other origami mentioned: Origami Stegosaurus by John Montroll YouTube Folding video (Part 1 of 3) Ilan Garibi’s Pineapple Tessellation (PDF instructions) Eric Gjerde Spread Hex Origami Tessellation (This also has the equilateral triangle grid needed to fold Inna’s gate logic) Peter Engel Amanda Ghassaei’s Origami Simulator (Mooser’s is under Examples->Origami) Some other math mentioned: Veritasium’s Math's Fundamental Flaw talks about Goerthe’s Incompleteness Theorem Physical Logic Game: Turing Tumble - Build Marble-Powered Computers Mathematics of Paper Folding (Wikipedia) Transcript Memfault is making software the most reliable part of the IoT with its device reliability platform that enables teams to be more proactive with remote debugging, monitoring and OTA update capabilities. Try Memfault's new sandbox demo at demo.memfault.com. Embedded.fm listeners receive 25% off their first-year contract with Memfault by booking a demo here: https://go.memfault.com/demo-request-embedded

Welcome to Embedded. I am Eliseo White. My co-host is Christopher White. Our guest this week is Ina Zagarevich, and we're going to talk about Turing complete origami, or paper computers, or algebraic topology, or something along those lines. Hi, Ina. Welcome. Hi. Thank you so much for having me. Could you tell us about yourself as if we met, I don't know, at a Cornell getting to know you parents day? Wow. I've actually never been to one of those um it would be scary but i'm going to pretend you're not scary parents um i'm a professor of mathematics i do category theory and algebraic k theory which when i'm trying to be funny and more philosophical i say that it means that I ask questions like, what is plus? And I think about them really deeply.

And when I am trying to be more serious, I say that algebraic k-theory constructs interesting measures on how important algebraic and generally mathematical objects work in terms of how you can pull them apart into pieces and put them back together. And these invariants turn out to be extremely important in that they show up all over mathematics and all sorts of different fields, but at the same time, they're extremely difficult to compute. So there's a lot of

technical theory about how you might go around analyzing or computing them. But I also don't actually do the computations. I mostly just show that various things are equivalent to various other things, which sounds like it's pointless, but it really feels to me like a sort of deep, important part of mathematics that we can we can say oh this thing is hard because it's very similar to this other thing which is also hard for better understood reasons um so i leave the computation to other people and i usually do this kind of analysis um and if i want to be silly again i say that i work on the theory of jigsaw puzzles which is also true knowing how hard things is it's very. We're going to end up talking about Galois Div 2 again, aren't we?

No. No. Good, good, good. We have lightning round where we ask you short questions and we generally want kind of short answers. And if we're behaving ourselves, we won't say, what and how, why and how is that possible? Are you ready?

I am ready. Favorite manifold? S2. Do you use a machine to pre-crease origami? No, although I have one that I've been wanting to make work for ages. And so far I have been a complete and utter failure in that respect.

So I would love to, but I don't because I'm a terrible failure. What kind of machine do you have? I have a Silhouette Cameo 4 Pro. Is there such a thing as a Hawaii double rainbow manifold, or is my retired math professor brother punking me? I mean, if he means a Hawaiian earring, then yes. Although I'm not sure it's a manifold. Maybe. I don't know. Think so? I'm not that kind of topologist, but

there is a thing called a Hawaiian earring, which is, that is definitely true. Interesting. What's your favorite origami animal to fold? Satoshi Kamiya's Pegasus, which was the first super complex thing that I folded. And I fell madly in love with it at around stage 70. And I think I folded about 10 of them, which given that each one takes me three to four hours is a lot. Favorite historical mathematician? Sophie Germain or Emmy Noter, depending on my mood. Yeah. Yeah. Excellent. Favorite current origami artist? Probably Satoshi Kamiya, which is not original at all because the guy is badass but satoshi kamiya oh and i love dosa severa's uh perpetua i don't think i've seen that one

but you should look it up it's amazing favorite fictional robot so it's murder bot by martha wells but it's not a robot. It's a construct. I got your answer. We had Martha Wells on the show. It was such a misuse of having a podcast and I loved every minute of it. She's amazing. I love her. It's anyway, whenever these days, whenever I read anything mediocre, half the time I'm thinking, I could just be rereading Murderbot. Why am I even reading this? And I got the audiobooks and I didn't think I would like that. And they're so good because they're so much slower than reading. It was so good.

I actually have both the audiobooks and the graphic audio adaptations. And I listen to all of them on rotation because they're so different and they're so wonderful in so many different ways. And anyway, I'm not going to turn this show into me squeeing about Martha Wells, but I totally can. Well, since I've already had a show where I got to do that, I understand. Do you have a tip everyone should know? Is it read Murderbot? I'd understand. The tip actually is if you want to get something done, give yourself a small amount of time a day where you have to do it. And don't worry about like putting in a large continuous block, even if you work better in large continuous blocks. I work better in large continuous blocks,

but I'm actually way better at getting things done effectively when I tell myself I have to spend half an hour a day and then I can spend longer on some days than when I just try to look for the long continuous blocks. I have been trying to do that for months, and it sometimes works, but sometimes I still need help getting the energy to do the 10 minutes. Yeah, there's a lot of self-discipline in starting. Yeah. And that's, yes, you make progress by starting, not by procrastinating trying to find the big times. Yeah, exactly. The big times when you're in the perfect mood to do it. Yeah.

We are happy to be sponsored this week by Memfault. Memfault provides a device reliability platform for IoT monitoring, debugging, and updates. Device operation no longer needs to be a scramble as issues with fielded units pile up. Instead, Memfault gives developers a more scalable and sustainable process to accelerate time to market, de-risk product launches, cut development costs, and deliver higher quality products. So if you're wondering how you're going to monitor your units once they're shipped, or whether your firmware update plan is secure enough, it's time to take a look at Memfault.

Or you can read their Interrupt blog for all of its fantastic goodies on how to debug hard faults, monitor units, or generally write good embedded code. Embedded FM listeners will get 25% off their first year with Memfault if you request a demo through go.memfault.com slash demo dash request dash embedded FM. It's a link you can find in our show notes. Thank you to Memfault for sponsoring this week's show. Okay. In the end, I want to ask you about making origami pieces that are Turing complete, but I think we have a few steps between here and there.

Can you tell me what it means to be Turing complete? So being Turing complete means that you can do anything that a Turing machine can do. So a Turing machine is like the most basic logical model for what a computer is. You should imagine it as like a little robot on a very long strip of paper, infinite in both directions. And the robot can look at this, the paper is divided into squares and each square has a symbol on it and nothing is a symbol. So this is how we think about it. And the robot can look at a symbol and think about what it's recently seen and possibly change that symbol and then move either to the left or to the right along that piece of paper. And it just does that forever.

And the robot only has a finite amount of memory in its head. So when I say what it's seen recently is maybe it has, I don't know, five or a hundred or four hundred thousand, but some finite number of things it can remember about what's going on. And those are the things that it can use to decide what to do with the square. And this is a nice sort of logical notion of what a computer is. And there's a bunch of theorems about what this little robot can accomplish. And being Turing complete means that you can do everything that this little robot can do, that this model of computation can do. So for example, something that's Turing complete, computers these days are theoretically Turing complete, but actually not because they don't have an infinite amount of memory, whereas

the paper strip has an infinite amount of memory. But if we had a computer with an infinite amount of memory, whereas the paper strip has an infinite amount of memory. But if we had a computer with an infinite amount of memory, it would be Turing complete. The Minecraft is Turing complete because you can actually build this little robot inside Minecraft. And assuming that your computer had infinite

memory and could build the entire strip, you can build a Turing machine inside Minecraft and therefore Minecraft is Turing complete. Magic the Gathering is Turing complete. Programming languages try to be Turing complete. Video games generally try not to be Turing complete, but sometimes they are for fun or accidentally. And so Turing complete means that it is programmable? It means that in some way, it can model the effect of a program running on a certain input. And it can model any program running on any input.

But the term programmable, I find a little bit fuzzy. So I'm not, I'm never quite certain how to answer that question. But morally speaking, it says, if you asked me, here's a program, here's an input. Can you model this program running on this input? In a Turing complete context, you can. Does it say anything about what kinds of problems can be solved? Or is that a separate theory? I don't really know how to answer that question.

Yeah, sorry. I may not know what I'm asking, so that's fair. Are there problems that are best solved with turning complete systems? I think about problems that cannot be solved with turning complete systems mostly chemical and biological but maybe that's just not i think i yeah i think it's a badly asked question on my part i think because it's a it's a computer so yeah what kinds of problems can you solve with computers lots of them so yeah okay it's really important to know what problems you can and can't solve with a computer because sometimes knowing that you can't do something is more empowering than knowing that you can so for example here's something you can definitely solve with a computer um the traveling salesman problem you have a map

you have a bunch of cities that the traveling salesman needs to visit, you know, the travel times between all the cities and you want to know what the shortest route for the salesman is so that they spend as little time in transit as possible. This can be solved with a computer, but we don't know of a way to find this in less than exponential time. So it's a very difficult problem to solve um and it's uh so the the idea is that this is the kind of problem that if you're trying to solve with a computer trying to get the best route is not a good idea And we can prove that it's not a good idea because it takes exponential time. But once you know this, you can say, oh, well, that's fine. I can, I've not,

I'm going to change my goal. Instead of trying to find the best route, I'm going to look for a good enough route, maybe one within 50% of being the best route or something like that. And so it's empowering knowing that you shouldn't keep trying to look for the best one because it's with modern technology, an intractably difficult problem. You should instead be looking for a good approximation. And I would just like to give a virtual fist bump to everybody who is currently saying simulated annealing. For example. And then go on and say, is that what NP-complete means? Or is that something else?

It's something like what NP-complete means, yes. That we don't, well, we don't know if P equals NP. So this is unknown, but I always felt that it wasn't. So it means that the only way that we currently know how to do it is exponential. And in addition, if we could solve this problem non-exponentially, we could solve every other problem that's in NP non-exponentially we could solve every other problem that's right right an np non-exponentially but right now the best technology that we have says that this is exponential okay so if you crack one np non-polynomial problem you crack them all if you crack an np complete

non-polynomial problem you crack them all yes. Yes. Which, I mean, if you could do that, you would be a wizard. And that would be awesome for lots of things. And you'd win a million dollars. All those salesmen would finally have optimal routes very quickly. I think the issue with factoring prime numbers would be the bigger one. Probably.

And dangerous. Factoring composite numbers into primes, not factoring prime numbers would be the bigger one. Probably. And dangerous. Factoring composite numbers into primes, not factoring prime numbers. That one's very easy. Yes, right. Even I can do that. Okay. So, Turing complete means it's computer-like,

for those of us who need to have tiny definitions. NP complete. Why is it NP complete? Why complete? It means it's hard. I don't remember what the complete means. The complete means that it's as hard as any other NP problem. Ah, okay. Okay. Because P problems are also in NP. So every problem, you know, the question of what's the smallest of this list of numbers, which is a linear problem, is also in NP, but I can solve that one in polynomial time without solving every NP problem in polynomial time.

Okay. Starting to remember. It's been a while. Okay. Cellular automata. Could you describe what those are? Okay. So cellular automata have,

well, they're like little cells. And I mean, I always think of them in very similar to Conway's Game of Life, which is a two-dimensional cellular automaton. But a cellular automaton is a bunch of cells sitting in some kind of geometric configuration. So the classics are a long line of cells and, or a grid of cells of some sort. Um, but let's just think about a long line. We have a long line of cells. So each cell

touches two other cells, the one on the left and the one on the right. And every stage, the cell is either alive or dead. They can come back to life. It's fine. Um, and you, so at every stage, the cell is either alive or dead. They can come back to life. It's fine. So at every stage, the cell looks at the two cells on either side and looks at itself and decides whether it's dead or alive in the next stage based on a very simple rule. And the only information it's allowed to take is its current state and the state of its two neighbors. Okay, I want to do Conway's life before we go back to that one, because I know we're going to be talking about that some more. Conway's game of life is like you've described, except it's a grid. Yes. And you're looking at your four nearest neighbors.

No, you're looking at your eight nearest neighbors. Or you do diagonals. You look diagonally too. Did you know that there is an encyclopedia of constructs and conway's game of life and it's still being added to and it's amazing because you can get little things that will shoot flyers and what are the other things yeah and there's blaster guns and spaceships and right there's little generators that shoot things right yeah yeah and you can also there's various theorems about like suppose i I have a spaceship that I wanted, which is a pattern that travels across the plane. It doesn't have to repeat itself perfectly every stage, but it goes in a cycle.

But between one period where it looks in a certain way and the next period that it looks in the same way, it's moved in a certain direction. So that's why it's called a spaceship. There are various people who try to construct a given spaceship with as few blaster guns as possible. And it's just incredible to watch how clever these constructions are. You just have blasters set up in the plane, shooting blasters at each, like shooting blasts at each other and then they create spaceships so you have this infinite string of spaceships coming out of like very and sometimes extremely complicated ones just from like a configuration of seven blasters okay i haven't seen i have not seen factories built in game of life that's really cool it's it's a it cool. It's a grid.

So let's say you have encode an array that is your current state. But each cell has its own state. You know, it's either on or off. Yep. And then it just looks at what's around it to determine if it's going to die of loneliness or die of overcrowding. Or come back to life because it has just the right number of people near it or cells. Same thing. And each one of these places, each one of these pixels acts independently.

Yes. And that's why they're called cells because they're each piece of code. And this is one of those things where you can write simple, very simple things, but get very complicated behaviors out of them when you start putting them together. And as I was putting together, as I was thinking about that and thinking about the show, how are these different than neurons in machine learning? I mean, I know the math is all different, but is it? I actually don't think it is. I think it's just that when you have a more complicated object to work with, you can encode more, more easily, but not necessarily more philosophically. Yeah, yeah.

Each cell is a little linear regression engine, I guess. But what if we stopped thinking about them as linear regression? Well, then you start, then you're Stephen Wolfram. Oh, okay. Yeah, I didn't read that book. I looked at buying it, but I didn't read it. Okay, so back to Conway's Game of Life. Sorry, it's a machine learning thing. I think someday I'll have a conversation about that, but not until my brain has stopped fizzing and saying, what if, what if, what if? Okay, so Conway's Game of Life is in 2D with a grid. And you mentioned being able to do this in 1D by having the center bit look at its two partnering bits as well as its own state.

And that brings me to rule 110. Yeah, so rule 110 is one of these cellular automata that's just on a line. And so again, each cell can look at itself and its two neighbors, and then it has to make a decision. And it's called rule 110 because if you write out the eight possibilities of what that cell can see. 1, 1, 1, meaning they're all on. 1, 1, 0, meaning the right-hand one is off, the cell itself is on, the left-hand cell is on, and so on down to 0, 0, 0,

which is they're all off. And then you write out the next state of the cell underneath it. And then read those eight bits as a binary number, that binary number is 110. And I mean that in base 10. It's, it's whenever 100 plus 10 plus one, it is not six. But you, you take the binary number, which is an eight digit binary number, and you read it in base 10, and then it's 110. So in fact, there's a rule n for every n from zero to 255. So rule 255 has all the cells. Everybody lives all the time. And rule zero is everyone's dead all the time and rule zeros everyone's dead oh the apocalypse rule yes the apocalypse rule

exactly um and then there's various other rules in between and rule 110 turns out to be Turing complete okay this rule for taking bits next to me suddenly now has the computing power of any computer yep i think it's magic okay okay i good good good because that sounded kind of we'll go with magic and not bonkers because who would say that i mean it's the great thing, it's the thing in math that I love the most that sometimes somebody tells you a result and you're like, absolutely not. No way. What are you smoking? And then, you know, you work through it stage by stage and you work through the proof and it's correct. And once you see the proof, you can't argue with it anymore. It's just there. And this is actually one of the reasons right now there's a big project to try to formalize

all of mathematics in such a way that a computer can verify every proof because mathematicians make mistake all the time. And when we write things up, we are not writing them up at the level where it could just be plugged into a computer. We're writing it at a level where another expert in the field can understand it. And that leads to mistakes. And so the idea is, well, but if we also had a formalized proof of everything, you would part of the job of doing a proof would be writing it up in such a way that a computer could verify it. And then plugging it into the computer and the computer will say, yep, this is a correct proof. And you'll know that you did something right. How far has that gotten? I mean, has it gotten all the way through Euclid?

I'm pretty sure. Right now, the next big push is for Fermat's last theorem. So I'm guessing, I don't actually know the state of Euclid, but I know they're working on Fermat's last theorem. I mean, that has a ton of sub theorems and things that it depends on include, including probably all of Euclid, but it's a, it's a huge project, but I have a friend who is doing, who is formalizing some proofs in algebraic topology. Um, and he said, this is Reed Barton, and he said this wonderful thing that I keep remembering,

which is this discussing with the computer what your proof says is a really great way figure out that you don't understand as much as you think you did. Is it easier to teach the computer or the students? Well, the computer only argues back when you're wrong, not when it's wrong. I see. We won't talk about the students then. One of the things about being a math prof is, or professional mathematician, is that you are proving things. And as an engineer, that is very far outside my scope. My scope is applications.

Why are proofs important? Oh, great, now she's not talking to me. No, you said it was okay to pause. I'm pausing it's it's kind of a yeah it's kind of a a big question why is breathing important i mean because you'll die if you don't that that one that was easier you're right i'm a mathematician so i have trouble only giving one answer. So here's an answer.

Historically, we have, as mathematicians, we haven't always had the same standard of proof that we have these days. It's actually a very modern invention, proofs of the standard at which we have now. It's only about 150 years old and which in math is very modern. The level of mistakes and of counterintuitive things that happen when you try to write down what mathematics is studying even is surprisingly high and the thing about proofs is that if you have a proof that a implies b then you don't know if a happens but you know that whenever a happens b has to happen and that kind of solidity is rare and beautiful and extremely reassuring, at least to me, because there are many things in life you can't control, but you can control proofs. At least once you have a proof. Before you have a

proof, it's all chaos and horror. But after you have a proof, you at least know that you're not lying to yourself. So here's a classic example of something like this. Suppose I have a continuous function. So just, you know, a function from real numbers to real numbers, whose graph I can draw without picking up my pencil. And now I'm going to take a sequence of these, and they're going to approximate some other function. So they're getting closer and closer and closer to some other function.

And I can ask, is that function continuous? Like, can I draw its graph with a pencil? And intuitively you think, well, of course, if you keep approximating it by continuous things, it's going to be continuous. But the answer, actually, nope, it's not. It won't necessarily be continuous. So imagine a step function. So it starts at zero and it stays at zero until you get to a half. And then it's going to rise very sharply until it gets to one and then it's going to stay at one. And so then as that steepness gets steeper and steeper and steeper you know

you can approximate that vertical line as much as you want but in the limit you can't have a vertical line on the graph of a function you're going to have to jump you're going to have to pick up the pencil the discontinuity yeah and so it's um and so this intuitive thing that, well, of course it's going to work, it's fairly easy to know when your intuition is not lying. If I tell you something about topological spaces... Which as far as I understand are all donuts. Yes, pretty much. That's a great way of visualizing. Donuts with different numbers of holes in various configurations. It's a perfect way to visualize topological spaces

but but you're already like getting something slightly off because donuts are smooth um a cube is also like the surface of a cube is also topological space but it has these points at the vertices where it's intrinsically pointed in a way that the donut never is. If you're a tiny ant on the donut, the donut always looks smooth. But if you're a tiny ant on the cube, you can tell you're not on a donut because sometimes you get to these pointy points. And no matter how far you zoom in,

they're always there. Right. And those are those places that are not differentiable right so that yeah okay yeah um and so if you want me to be more technical i can be more technical but honestly our listeners will hate us i'm trying no it's fine i think of them i personally think of them as pointy points but i'm also not a geometer so um but then in addition I can tell you something so surprising that you won't believe me. And then the question becomes, you know, can I convince you that it's actually true? So here's an example of something that a lot of people have trouble visualizing.

Take all of three-dimensional space. And I don't like the fact that there's all these different bits of infinity going off in different directions so i imagine myself taking all of the points at infinity and drawing them up into a single point okay so instead of now having you know different infinite directions wherever i go uh i always end up in the same place where i when i go to infinity. And the way you can think of this is like it's the difference between a plane and a sphere. I've taken all of the edges of the plane and I've wrapped them up into a single point.

And that's the North Pole, say, and you're wrapping it around the sphere. And so now you've closed it up and it becomes a sphere. If you do this for space, you get what's called the three-dimensional sphere S3. And the statement is that I can decompose S3 into two donuts, which are linked and which each have one hole. They're honest donuts. And you can decompose S3 into two donuts and they intersect at the surface of the donut. And when I tell people this at first nobody believes me because what are you talking about the outside of a donut in space is not another donut but what i'm telling you is that yes because of the infinite bits but if you gather all the infinite bits into one place

it will be a donut excuse me i have to go get some coffee and what and so what is the okay i'm not arguing i'm trying to understand so what is the, okay, I'm not arguing. I'm trying to understand. So what is the justification for the step where I can take all of the infinite points and merge them? So there's two kinds of spaces. Let's go down a dimension and look at two-dimensional

things. We can have a plane, which is sort of infinite, and we can have a sphere, which is finite, and it's in fact compact, which is sort of infinite and we can have a sphere which is finite and it's in fact compact yes which is what the actual important part um and wait wait is compact just mean that it is the smallest uh circumference outside to inside thing no compact compact means that it behaves like a finite object in as much as a thing with infinitely many points in it can so here's an example um if i'm on the plane i can walk in any direction and just keep going and i'll never get anywhere i can just keep going forever

and ever yeah infinite but honest infinite but in sphere, if I keep walking around the sphere, there's going to be some spot on the sphere that I keep coming back to. I'll be keep coming closer and closer and closer. Maybe I'll never get to that specific point, but there'll be somewhere, you know, where you can put a post on this, on the sphere. You know, if you know how I'm walking on the sphere, then you'll be able to put a post on the sphere so that I will, I will keep coming back to within an arm's length of that post. Okay. I can't get away from it.

That's what compact means. Okay. Technically it's what sequentially compact means, but anyway, for things like spheres, it doesn't matter which one you take. Okay. We were talking about proofs.

And so you're telling us, okay, so this, this example of sphere becomes two toruses. Two solid toruses, yes. And so the justification is there's no way that you can take two solid toruses and glue them together into something infinite, right? So I have no chance of making this true if I work in something that's infinite.

But in fact, quite often working in something that's infinite is just bad. Yes. We don't like to do it. We prefer things that are compact. And adding this extra quote point and infinity is a very standard way of making space compact. Okay. So this is a very common object. It comes up all the time.

And so somehow cool decomposition theorems about it comes up all the time and so somehow cool decomposition theorems about it are a fairly standard thing to do okay i feel like i saw that somewhere in the past in physics but i don't remember where the context was but yes okay alicia you're here i have the crazy eyes yes okay this is this is the thing that's so great about proofs. Like, I can write down the formulas for this, and you can go over them, and you can, even though you can't visualize it, you can agree that mathematically it has to be true. Each step follows another step logically and mathematically. Each of those is small enough to understand, and they lead to the inevitable conclusion, even if it's counterintuitive. Yes. And I love the counterintuitive ones more than anything else because they're so great. I think the best referee report I've ever gotten on a paper was a very negative report that said, this paper can't possibly be right because K-theory doesn't work like that.

And I was so proud of it. And of course it was right. Oh, it was right. Yeah. Okay. So, so you like bending brains and you like the reassuringness of being sure you're right. And the two together is just the best thing ever. You also like bending paper.

How was that? Was that a very good segue? It's a fantastic segue. Definitely. What kind of origami do you usually do? It depends on whether I want to focus on something and I have the time and space to focus on something or whether I'm doing this in between running around with the kids or traveling or, um, you know, sitting in a conference when I'm trying to pay attention to talks and that's not too much to my origami. Let's do the focused one because the other ones are, are toys and,

and, and distracted. So yes. Okay. Yeah. So the ones where i can focus i like super complex animals i think they're just amazing and lots of fun and um i think i have about 10 super complex books i haven't done anywhere near everything from them there's certain things that i haven't quite been brave enough to. Satoshi Kamiya has the Ancient Dragon, which is done on a 70 centimeter by 70 centimeter piece of paper. And I desperately want to do it, but I haven't been brave enough to do it yet. But I do, but that's what I tend to do when I can really sit down and focus. So again, I like Satoshi Kamiya's Pegasus. I've done the Divine Dragon Bahamut that he has in his first book four times, largely because I've never done one that I felt completely satisfied with. It's a very difficult 200 plus step

fold, but it produces this amazing dragon, which I think is from final fantasy seven. Um, and it's standing on its hind legs and it has these giant wings and it's amazing. And I love it. And I want to make the most beautiful version of it that I can. And so I keep coming back to it. I also in a cuter version, um, found this origami model of the rat from Ratatouille that I've made four or five times now. I think it's adorable. It's wearing a chef's hat. The chef's hat is made from the opposite side of the paper, so you can make it so that the rat is gray and the chef's hat is white as it ought to be all from one sheet of paper. Peter Engel also has this great kangaroo with a little baby kangaroo in this pouch.

That's one of my favorites when I want to make something faster. And, you know, as a very classic, John Montrell has his Stegosaurus, which is beautiful. And actually, I have one right here in my office with me. Yeah. I'm using this for ideas, even though this isn't really what I usually fold. What do you usually fold? I really like curved creases.

So I do a little bit of pattern development for tessellations and corrugations, but I also like curved creases in animals. So I have a jellyfish and an octopus and some snails that use the curved creases to do a 3D effect that's smooth and biologically relatable. Oh, that's amazing. That's wonderful. I've never done curved creases because I don't like scoring. You need your silhouette system. Yeah. Yeah. Yeah. And so I've always looked at it. It's so amazing. I think it's incredibly beautiful, but I've never done any. The fluidity is really, really nice. But yeah, after about 80 steps on one of the other ones, I get frustrated.

Even though I have, I mean, there are some patterns that flat land. You do those tessellations, which seem like they have thousands of steps, but they're repeating steps. Repeating, I see. What's your favorite tessellations which i do like they have thousands of steps but they're they're repeating steps yeah what's your favorite tessellation uh usually whichever one i folded last um you like the ones with the negative what is it yeah so anything in the mirror or folds. I was working on trying to combine some Miura Ori style things with curves. I say that because I'm looking at one I gave to Christopher. That's all I can think about. That sounds really cool.

But it's not like Mooser's Train, which is box pleated and a thousand amazing detailed steps to get something. Oh, I haven't done Mooser's Train, but I have the book and I really want to. Are you familiar with the Origami Simulator? No, I'm not. I have no idea what that is. It's so cool. It's origamisimulator.org. Amanda Gossi did it, and it has a whole bunch of example patterns. And then you slide the little slider, and it goes from a flat page to folded origami. and sometimes if you put in your own patterns it will tell you that that's not foldable or it will just kind of collapse in a billion little grid steps that didn't succeed

guess which one i like to do that sounds really awesome i have not looked at it before i've done some tessellation like some designing of tessellations but honestly if i'm going to spend hours on like thinking through something i'd rather do something by satoshi kumiya because i feel like it's very challenging and it's like a you know wow look at this amazing thing can i do it and with uh tessellations which by the way i fold all the time they're just more of my like conference travel kids folding mine too um that uh that are all that could also be extremely challenging but i always felt like they always feel more within reach for me which is why i tend to when i want

to focus on something i don't reach for them. But I would have called your Nanden Norgates made out of origami to be on the tessellations spectrum more than. Oh, they definitely are. Yeah. No, they definitely are. There's one of the things they were inspired by was origami tessellations. Um, but, uh, I'm not, look, I just in my office, which is where I fold when I'm really stuck on something, I have a pile of at least 20 tessellations that I've made within the past few months. I fold tessellations all the time. I think they're really awesome. I just, you can't make a tessellation with 250 steps

because the piece of paper you would need is going to be too large. Yeah, I mean, it depends on how you call the steps, but yes. Because it is usually a repetition. You don't, if you're folding something 32 times horizontally, that's kind of one step. Yeah, that's, that's, that's exactly how I think about it. When, you know, my favorite tessellation is probably Elan Garibi's pineapple. Oh yeah. That's a nice one. A good way to take a big piece of paper and make it into a little piece of paper yes exactly um it's it's very it's a it's a very challenging collapse also especially because it's a two-stage collapse i've always

wanted to make his like multi-stage like three or four stage pineapples too and designing it like it's a brilliant feat of design um but i always feel like if I can fold one cell, I can fold all the other cells too. And it could be really hard, but I can do it. And so you fold one or maybe you set up a paper to fold them all. But after you fold one, it's a way of occupying your hands while your brain is doing something harder. Yes. Whereas something like the divine dragon, it's every step is different. Every step is asking you to do something else. Every step is making you think about what's going on with the paper in a different way. Yeah. And then the only time I get really excited about the tessellations that aren't curved is when I look down and realize that

I made a mistake and it's really interesting. How do I do that again? Okay. Sorry. Sorry. Yeah. We got distracted by origami. So you said you can make logic gates out of origami. I think that's where all this was headed, right? Yes. And NAND and NOR, I mean, I feel like once you have those, you can get to Turing complete because that's how computers are made. Pretty much, yeah. But you wrote a paper about Rule 110 and paper. Could you talk about that?

Yeah, so this is going to be a plug for Veritasium because Veritasium is awesome. But I was watching the Veritasium video on girdles and completeness with my son and my husband. Also, just as a fun comment, they have a minor error in the first five minutes or so. And my husband made me pause the video and like to go on an explanation to my son about why it's wrong. And I was like, I'm going to fix it. And then it's down the line. Cause I've seen it before.

And my husband was like, no, that's not the point. It's wrong as it's stated now. And it's kind of on brand for being something about the incompleteness. Yes. Anyway, it's, uh, it was really great. It's a really wonderful video. And it mentioned that the game of life is Turing complete. Um, it also has a great little clip of a Turing machine being modeled inside the

game of life that I actually rewatched that little clip like six times because it was amazing. Um, and I've always liked the mathematics like six times because it was amazing. And I've always liked the mathematics of origami because I like mathematics and I like origami. And why not put the two things together? Why not both? And I was sitting there going, the game of life is really simple. I bet origami is harder.

And I'd seen results saying like flat folding origami is NP hard. And I thought, well, if it's NP hard, it's got to be Turing complete. It just has to. The NP hard paper did like gates and it's got to be Turing complete if you did an infinite sheet of paper. And so I wrote to Tom Hall, my collaborator, and I was like, hey, do you know if this is true? And I was expecting him to say, oh yeah, this is well known. Here's the paper. You know, thanks for writing. And instead he wrote back saying, I don't know. That's a good question. Do you want to try to work on it? Um, and so we did, uh, we sat down and, uh, we worked on it and building gates is surprisingly hard, but the other thing, you know, other papers have done similar things, but actually figuring out, okay, if you want to show something is Turing complete,

you need to find another thing that is Turing complete, like a Turing machine or the game of life or something like that. And you need to model it with your chosen medium. And so... Rule 110. Rule 110. So in fact, originally I was trying to model the game of life. Um, and so, you know, I thought, okay, the standard way to do, uh, you know, transfer of information on a piece of paper is via pleats. So if you have a piece of paper and you can lead it, just make a valley fold and then a mountain fold that are parallel and you get a little pleat in the paper

and depending on which direction you fold those, what order you choose, the paper will either point left or point right. Okay. And with that, you can transfer some information, like which direction did you choose? That's a bit of information.

So that's the standard way to sort of translate information down the, down the page. And, and so I was trying to build this eight fold thing, which would take eight pleats coming in around and would either twist to the left or twist to the right, depending on how many of the pleats were on and how many were off. And I could not get it to work. I tore a bunch of sheet paper trying to get this to work and I could not get it to work. Uh, probably a better origami designer than I am would be able to do it, but I couldn't. And so I went online and I looked for a list of things that are Turing complete and uh there is a list online of things that are Turing complete including Magic the Gathering

and Minecraft and a bunch of other things and I knew I wasn't going to be simulating Minecraft in origami so that one I just crossed off list, but I was looking for the simplest things I could find. And I saw this rule one 10 and I had no idea what it was, but I looked up and I thought, okay, three inputs. Do you know what you can do with, if you have three inputs and one output, that's only a fourfold object that you need to make. But even more than that, if you're trying to transfer information down the paper, if you're trying to transfer information down the paper, if you think about a hexagonal twist, which has six pleats meeting in the center, it has three inputs and three outputs, which is actually exactly what you want,

because a cell sees the three cells above it. So, sorry, what above? I mean, before it, a cell looks at itself and the two cells next to it. So you have input from three different cells, you in the past, person to the left on the past, person to the right on the past. And then you have three different outputs to yourself in the future, person on the left in the future,

person on the right in the future. And that's a six-fold object. And I know how to make a six-fold object. There are these things called hexagonal twists that take six pleats coming in in a spiral and sort of twist them together so that they fold nicely. grid that naturally forms into hexagons. So this feels like it actually naturally fits into the kinds of origami tessellations that I know how to fold. This seems a lot more promising. The way you're talking about this makes the Conway's Game of Life even less promising, because it isn't just eight in, one out. Yeah, exactly. It's nine in, really, because you also need to have your previous input

and nine out and nine out yeah and also the output sort of needs to go vertically rather than you know horizontally and paper is not 3d i think game of life was a bad idea i can see how you got there but i'm glad you found something simpler so that's the um so that was the the start it was really just looking through this list of things that are turning complete but once i was like okay so i you know the simplest kind of logic i can build on a hexagonal grid is gates so can i build gates so tom and i met and we discussed and I explained that, okay, if you want to write rule 110 just in terms of gates, you can write the formula in terms of NAND and NOR and, you know,

or AND and OR in various ways. We had several ways of writing it. So I was like, okay, so if we want to do this, we need to write, make gates. And Tom was like, okay, but I don't quite know how to do that. And I was like, okay, but let's work on it. So we worked on it for a bit and we came up with these gates. And we're slightly cheating with these gates because the traditional flat folding origami mathematical question is, I'm giving you a crease pattern. And the question is, will it fold flat? That's the question, right? But I couldn't get it to work that way at all.

I spent a couple of weeks working on it and I could not find a way to make a logic gate using that. Again, I invite, please, somebody who is more clever than I am, please come up with a way to do this because I would love to see it. What I did was I added optional creases. So there are creases that have to be folded. And then there are other creases that you can fold or you can keep flat. It's fine. But you're not allowed to crease anywhere where there wasn't a pre-drawn crease. And in fact, in our first version,

we had optional mountain folds, optional valley folds, and optional bi-directional folds that could fold in either direction. And I really hated the bi-directional folds because they're just super duper cheating. We're already cheating by adding optional folds, but now we're also adding bi-directional folds. The classical origami questions either have no assigned directions or all of the directions are assigned. The fact that you can do some directions assigned, it just felt horribly like cheating and I was very unhappy with it. And Tom, who is a practical and reasonable person said, it's okay. Let's see if we can do it with these. And then, you know, and then maybe we can discuss. Optimize later. Yeah. Optimize later. So, uh, we, so we, you know, and we couldn't quite

figure out how to do it. And then I was at this very boring talk at a conference. I won't tell you whose talk it was, um, but I was at a very boring talk at a conference. I won't tell you whose talk it was, but I was at a very boring talk at a conference and I had my origami paper with me and I was planning on folding spread hexagons, which is an Eric Gierda tessellation. And it's one that's nicely takes more attention and I could sit there and pretend to be listening. Well, not listening at all.

And I started folding this triangular grid that you need for it. And then I started thinking about this discussion that Tom and I had. And instead, I started trying to fold a gate. And in fact, the first gate that we folded was a NAND gate. I thought it was an AND gate for a while, but I was wrong. It was a NAND gate. That was the first one we managed to do with bid-directional creases. And I was so excited. And I wrote to Tom saying, hey, I managed to make an AND gate. Actually, I wrote, I managed to make an AND gate, but let's pretend I didn't make that mistake. And Tom was quite excited. And I sent him the crease pattern. And he wrote back saying that he thinks it works.

And he wanted to fiddle with it too. And the next day, he sent me an or gate. And I was like, okay, well, we're in business. You know, once we have and, and, or, like what else do we need? We need a not. Not's gotta be easy. And not actually turned out to be

one of the harder ones amusingly. But we did it. We had all these bi-directional folds on it but it was fine we just wanted to sit down and write it out properly and then tom was like hey ina i don't know if you know but there's this classic mistake in origami uh computability stuff where the issue is that intersecting pleats can interfere with one another badly. Like they can shift the signal and they can start interfering with one another from arbitrarily far away, and it's bad. And I said, we won't have the issue with things interfering from arbitrarily far away because we're working on a grid. And so, you know,

you can't have, you know, a priest coming up at a weird angle, that's going to start interfering and just getting more and more and more of them because we're on a grid. And Tom was like, yes, that's true. That's a great point. And then I said, but and then I said, and I was very confused. I said, how can intersecting things cause a problem? When I'm doing tessellations pleats intersect all the time and it's never a problem um and tom said no but classically it is like doing it without interfering with the signals is really hard and i was like i don't think that's true but let me try to figure it out and tom's like yeah we have this result that we managed to

prove that intersecting pleats at a 90 degree angle is fine and you can do it just fine but at other angles I'm not sure you can do it and I was like no no no at 60 and 120 degrees you definitely can do it like you know you've you've folded tessellations you know it'll be fine works fine and Tom was like well you know traditionally there's some problems. It works fine. And Tom was like, well, you know, traditionally there's some problems with it. And so I sat down and I wrote down the intersector, which if you look in the paper is the longest section in the paper, proving that the intersector works and the way it works is exactly the way you expect it to work. You have a pleat, you have another pleat that pleats that pleat and everything is fine. Proving that that thing worked took three

weeks. See, that's where it's really annoying when you know your intuition is right, but it's really hard to prove it. But what if something really weird goes wrong? I've definitely had things where my intuition is like, oh no, this will totally be right. And it's just wrong. So having the proof was very comforting that was probably that was that was very intense and then just as i was finishing writing up the proof for the intersector tom wrote to me being like hey i figured out how to do a knot without bi-directional creases and i was like that's cool now we got to get rid of them on everything else and i was like no it's fine and i was like no we have to get rid of them on everything else and I was like no it's fine and

I was like no we have to get rid of them on everything else if you can get rid of them on the hardest one you can get rid of them on all of them exactly plus the intersector didn't have any bi-directional creases it was all single directional creases so I was like no the two hardest things had no bi-directional creases there There's no bidirectional creases needed. It'll be fine. And so we spent another week or so on it and we managed to get rid of the bidirectional creases and I was very happy. And then we had to go back to simulating rule 110.

And again, Tom was very, Tom was the practical one here. And he said, let's do something simpler let's do a schipinski gasket which is really just uh checking whether two inputs are equal or not if they're equal you spit out zero if they're not equal you spit out one that's what the mod two schipinski triangle is um and you can in fact you can do this if you start with sort of a triangular grid and you put a row of zeros in and you put in a single one and then at every point you take the the sum of the two cells above a cell and you put that in the next cell so then the next row will be one one and

then a row after that will be one zero one and And you keep going, you get this, you know, you get the Scherpinski triangle going on forever and it's fun. And so Tom was like, let's see if we can just do that. It'll be a simpler crease pattern. And I was like, you're right. And I sat down and I planned it out. And again, if you look in the paper, you can see you can see the layout of the Scherpinski gasket, which takes, I think, 18 different gadgets. Because actually checking whether two signals are equal using gates is surprisingly difficult.

I'd never thought about it, but it is. But in addition, you need to do this complicated thing where you need to reflect a signal and that was the thing that actually took me the longest to figure out how to do what you want to do to check that whether two signals are equal so suppose that you have two signals a and b and you look and you see okay you look at A and not B and if you have A and not B that means that A is true and B is false so they are different um the other way you look at, um, not A and B, and again, you look, this, this tells you whether A is false and B is true. So those are the two cases when they're, when you can pick out that they're different.

And then you look at those two signals and if either one of them is true, then your two signals are different. And, uh, and if the, if neither one of them is true, then your two signals are different. And if neither one of them is true, then your two signals are the same. So you take those two and you put it into or, and that tells you whether the two signals are different or not. So you have one signal which is a and you have one signal which is b and now you need to split them compare them in different ways and recombine

and when you're doing this with origami your signals have a direction it's not like with wires where you can loop things around however you like. Your signals are straight lines. So you have a signal and you split it into two and they go off at a set angle. The two signals go off at 120 degrees. So they're going in two different directions. But you want them to end up in the same place because you want to put them into these two AND gates and then you want to put them into these two NAND gates and then you want to recombine them. So you want to be able to reflect a signal. One of these signals is sort of going

towards your computation bit and the other one's going away and you need to be able to reflect it back into the center. And that was actually the hardest part of the whole thing. How do I reflect this signal? Keys and getting the signal where you want it to go. It sounds like you can build a computer out of waves. Oh, that would be really cool. So you're talking about these signals and they're being reflected in folds that are, I presume they're moving some way, right? You're refolding. Oh, no, no, no. The idea is you're never refolding. The question that you end up asking

is, will this fold flat ever or not? Okay, right. Got it. Okay. So I'm thinking about this somewhat the wrong way. Yeah, we're not moving the paper. Yeah, okay. We're folding all the things flat, and it's the initial conditions. Gotcha. Okay, so it's a single computation is the fold, the complete set of folds.

Okay, cool. Got it. How many of these do you have in your office? I have gates. I have a lot. What about a full rule 110? Zero. Really? Rule 110s.

I even have zero Sierpinski gaskets, largely because I tried to fold it from one very large sheet of paper that I folded a 128 grid on. And it's really hard to fold, it turns out, because there's so little regularity to what's going on. Usually on a, on a like tessellation, I start in the middle where I started one of the edges and there's enough regularity to what's going on that I feel like I have some control over what's going on. And with this large paper, I felt like I just had no control over anything. And at some point,

the plan is to sit down and sort of draw on the paper exactly where I'm planning to put everything and then try it again. But usually I don't plan like pre-crease for me and then I could color in using the same colors you have in your paper. That would be awesome. There's no way I could just remember. But then a couple of weeks ago, I was looking at this pattern again and I was like, I could do this modularly and I know how to do it modularly. So my current plan right now is I have these hexagons that I cut on my silhouette. And the plan is to fold modular bits of this pattern and put them all together and attach them to each other with paperclips and see if it'll work that way. And then it'll look like a circuit and it'll be great. That would look really cool. So that's the current plan.

But I have zero of these currently folded. Individual gates I have a lot of because I tend to give them away and then somebody wants to play around with one so I make another one and then I tend to give those away and so on and so forth. You could use magnets instead of paper clips

too. Then you could just pick them up and put them around in a different NAND NOR configuration. Oh, that would be really cool. Do you know the game Turing Tumble? No. It's this amazing game that, I mean, my kids loved it, but it's pretty much... Marble-powered computers?

Yes! It's marble-powered computers. And also, all of the pieces work in this extremely satisfying, beautifully engineered way. So it all clicks together in just this amazing way. It's pretty much programming problems. It'll tell you, oh, you have these limitations. You have to use these parts and you're allowed to use these parts. And you have a blue marble input and a red marble input. And your output needs to be two blue marbles and a red marble, two blue marbles, a marble two blue marbles a red model verbal etc etc how do you do it and the the point is you could just set up the parts and then you hit the the lever to make it go and it goes clickety clickety clickety clickety clickety and it it's beautiful and i think would be really amazing to make an origami gates version of this but you know i'm not a game designer, especially not one as brilliant as the ones who made that game. So this is on my wish list for the world. I had plans this weekend.

Did you? I did. They involved origami, but not this. All right. Well, this looks really cool. Do you have SVGs of the patterns? I do. Actually, they are entirely made in Tixi. So I can send you the Tixi code.

Both the Shapinski triangle one and the rule 110 one are just code in Tixie, and I'm happy to send it to you. It's actually also available in archive because, you know, you can download the tech code and it's just in there. What's Tixie? Tixie is a graphical package for LaTeX. So it's just like... This just keeps getting worse and worse. Remember, she has to write actual academic papers. She can't just put stuff on

GitHub and call it a day. How many Python collabs do I have for my origami? Quite a few. I, uh, yeah. So, let me tell you something funny. At the joint math meetings, which is the largest

math conference in the U.S., I don't know about the world, but it's is the largest math conference in the U S I don't know about the world, but it's definitely the largest math conference in the U S it happens yearly in January somewhere. And this year it was in San Francisco and they had a set, a session on serious recreational mathematics. And it was one of the most amazing mathematical sessions I've ever been to. And I hope they have more. It was just amazing. And Tom Hall Hall my collaborator

spoke about uh about this paper and prior to his talk there were these amazing videos of giant sheets of plastic auto you know folding up into bus stops and these amazing simulations of fonts shifting into one another. I was very impressed by, um, but you know, there was a lot of computer science people there. It was, I don't know if it was just not impressive or what, but I thought they were amazing. Uh, and then my collaborator showed them this picture of the Rule 110 cell. And he said, and this was made by hand in Tixi. And there was a gasp through the room. Like an audible gasp.

I was like, this is not, I don't know whether that's a horrified gasp. It might be a horrified gasp. Because while I was making this, I was definitely sitting there thinking, I should come up with an automated way to do this where i can just like tell it the coordinates of gates and it'll generate everything on on its own and then i was like but that would take me longer than six hours and this will definitely take me less than six hours to do by hand so i should be doing it by hand depends on how many more times you want to do it. Exactly. So this is the question, am I ever going to do it again? And, you know, maybe, and so maybe I should have done an automated

thing, but everything in this paper is done by hand. And in fact, you can, if you download the LaTeX code, you can see how it's all done. Okay. Well, I may need help with that, but you will be the second person to ask for help. Excellent. Christopher looks away, knowing he's the first. Don't make me do math. It's been too long. I'll make you do LaTeX. No, don't make me do LaTeX. It's been even longer. That's almost worse.

I was really good at it at one point. In the 90s. My website is still from the 90s. This has been very interesting. And now I have so many more ideas from cellular automata and neural networks to new folding ideas to game design with origami. I think you should pick one. My brain is fizzy. Do you have any thoughts you'd like to leave us with, Ina? There's a comment I sometimes get from serious mathematicians

who don't do things like origami math in addition to other math, which is why, why would you do this? What, what is the point? Who cares? And the point is that it is awesome and cool. And that's why I did it. And I think that people should do more awesome and cool things and worry a little bit less about why they're doing it there's always applications later that somebody else can figure out oh my god and it's just cool so don't worry about it the rigid foldability and and and and then we can go on to to like flex circuits in this and I'm on board with stop worrying about why. That would be so cool.

Our guest has been Ina Zekerovic, professor of mathematics at Cornell University. Thanks, Ina. Thank you so much. Thank you to Christopher for producing and co-hosting. Thank you to our supporters on Patreon, and thank you to Memfault

for sponsoring this week's show. You can always contact us at show at embedded.fm or at the contact link on Embedded FM. Or you can go to Amazon and buy my book, Making Embedded Systems, Second Edition. And now I have a quote to leave you with from Alan Turing.

Machines take me by surprise with great frequency.