474: It's All Chaos and Horror
Transcript from 474: It's All Chaos and Horror with Inna Zakharevich, Christopher White, and Elecia White.
EW (00:00:07):
Welcome to Embedded. I am Elecia White. My co-host is Christopher White. Our guest this week is Inna Zakharevich, and we are going to talk about Turing-complete origami. Or paper computers. Or algebraic topology. Or something along those lines.
CW (00:00:25):
Hi, Inna. Welcome.
IZ (00:00:27):
Hi. Thank you so much for having me.
EW (00:00:30):
Could you tell us about yourself as if we met, I do not know, at a Cornell getting to know you Parents' Day?
CW (00:00:39):
<laugh>
IZ (00:00:44):
Wow. I have actually never been to one of those. It would be scary, but I am going to pretend you are not scary parents. I am a Professor of Mathematics. I do category theory and algebraic K-theory. When I am 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.
EW (00:01:07):
<laugh>
IZ (00:01:09):
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. These invariants turn out to be extremely important in that they show up all over mathematics in all sorts of different fields. But at the same time, they are extremely difficult to compute, so there is a lot of technical theory about how you might go around analyzing or computing them.
(00:01:44):
But I also do not actually do the computations. I mostly just show that various things are equivalent to various other things, which sounds like it is pointless. But it really feels to me like a deep important part of mathematics that we can say, "Oh, this thing is hard because it is very similar to this other thing, which is also hard for better understood reasons." So I leave the computation to other people, and I usually do this kind of analysis.
(00:02:13):
If I want to be silly again, I say that I work on the theory of jigsaw puzzles, which is also true.
CW (00:02:21):
Knowing how hard things is is very important.
EW (00:02:23):
We are going to end up talking about Galois div two again, are we not?
CW (00:02:26):
No.
IZ (00:02:28):
No.
EW (00:02:29):
Good. We have lightning round, where we ask you short questions and we generally want short answers. If we are behaving ourselves, we will not say, "What?" and "Why?" and "How is that possible?" Are you ready?
IZ (00:02:44):
I am ready.
CW (00:02:45):
Favorite manifold?
IZ (00:02:47):
S2.
EW (00:02:49):
Do you use a machine to precrease origami?
IZ (00:02:52):
No. Although I have one that I have been wanting to make work for ages. So far I have been a complete and utter failure in that respect. So I would love to, but I do not because I am a terrible failure.
EW (00:03:04):
What kind of machine do you have?
IZ (00:03:06):
I have a Silhouette Cameo 4 Pro.
CW (00:03:09):
Is there such a thing as a "Hawaii Double Rainbow manifold," or is my retired math professor brother punking me?
IZ (00:03:16):
If he means a Hawaiian earring, then "Yes." Although I am not sure it is a manifold. Maybe. I do not know. Think so?
CW (00:03:23):
<laugh>
IZ (00:03:23):
I am not that kind of topologist. But there is a thing called a "Hawaiian earring." That is definitely true.
CW (00:03:31):
Interesting.
EW (00:03:31):
What is your favorite origami animal to fold?
IZ (00:03:37):
Satoshi Kamiya's Pegasus, which was the first super complex thing that I folded. I fell madly in love with it at around stage 70. I think I folded about ten of them, which given that each one takes me three to four hours, is a lot.
CW (00:03:49):
Favorite historical mathematician?
IZ (00:03:52):
Sophie Germain or Emmy Noether, depending on my mood.
EW (00:03:56):
Yeah. Excellent. Favorite current origami artist?
IZ (00:04:01):
Probably Satoshi Kamiya, which is not original at all, because the guy is badass. But Satoshi Kamiya. Oh, and I love Dasa Severova's Perpetua.
EW (00:04:14):
I do not think I have seen that one. Excellent.
IZ (00:04:16):
But you should look it up. It is amazing.
CW (00:04:18):
Favorite fictional robot?
IZ (00:04:20):
So it is Murderbot from Martha Wells.
EW (00:04:22):
Oh, yes!
IZ (00:04:22):
But it is not a robot. It is a construct.
CW (00:04:25):
Okay, now I get your answer.
EW (00:04:28):
Yes, that is fair. We had Martha Wells on the show.
IZ (00:04:29):
Oh my God!
EW (00:04:29):
It was such misuse of having a podcast. I loved every minute of it!
CW (00:04:33):
<laugh>
IZ (00:04:35):
She is amazing! I love her.
EW (00:04:36):
So amazing.
IZ (00:04:36):
Anyway, these days, whenever I read anything mediocre, half the time I am thinking "I could just be rereading Murderbot. Why am I reading this?"
EW (00:04:46):
I know!
CW (00:04:46):
<laugh>
EW (00:04:47):
I got the audio books. I did not think I would like that. They are so good, because they are so much slower than reading. Oh, it was so good.
IZ (00:04:55):
I actually have both the audio books and the graphic audio adaptations. I listen to all of them on rotation, because they are so different and they are so wonderful in so many different ways. Anyway, I am not going to turn this show into me squeeing about Martha Wells, but I totally can.
EW (00:05:13):
Well, since I have already had a show where I got to do that, I understand.
CW (00:05:15):
<laugh>
EW (00:05:15):
Do you have a tip everyone should know? Is it "Read Murderbot"? I would understand.
IZ (00:05:22):
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. Do not worry about putting in a large continuous block, even if you work better in large continuous blocks.
(00:05:35):
I work better in large continuous blocks, but I am actually way better at getting things done effectively, when I tell myself I have to spend half an hour on it a day. Then I can spend longer on some days, than when I just try to look for the long continuous blocks.
CW (00:05:47):
I have been trying to do that for months. It sometimes works, but sometimes I still need help getting the energy to do the ten minutes. <laugh>
IZ (00:05:56):
Yeah, there is a lot of self-discipline in starting.
CW (00:06:00):
Yeah.
EW (00:06:02):
Yes. You make progress by starting, not by procrastinating trying to find the big times.
IZ (00:06:09):
Yeah, exactly.
EW (00:06:10):
The big times when you are in the perfect mood to do it. Yeah.
IZ (00:06:12):
<laugh>
EW (00:06:12):
<music> 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.
(00:06:46):
So if you are wondering how you are going to monitor your units once they are shipped, or whether your firmware update plan is secure enough, it is 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.
(00:07:04):
Embedded.fm listeners will get 25% off their first year with Memfault, if you request a demo through go.memfault.com/demo-request-embeddedfm. It is a link you can find in our show notes. Thank you to Memfault for sponsoring this week's show. <music>
(00:07:21):
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"?
IZ (00:07:42):
So being Turing-complete means that you can do anything that a Turing machine can do. A Turing machine is the most basic logical model for what a computer is.
(00:07:55):
You should imagine it as a little robot on a very long strip of paper, infinite in both directions. The robot can look at- 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.
(00:08:14):
The robot can look at a symbol and think about what it has recently seen, and possibly change that symbol. Then move either to the left or to the right along that piece of paper. And it just does that forever.
(00:08:30):
The robot only has a finite amount of memory in its head. So when I say what it has seen recently, is maybe it has, I do not know, five or a hundred or 400,000, but some finite number, of things it can remember about what is going on. Those are the things that it can use to decide what to do with the square.
(00:08:52):
This is a nice logical notion of what a computer is, and there is a bunch of theorems about what this little robot can accomplish. Being Turing-complete means that you can do everything that this little robot can do, that this model of computation can do.
(00:09:12):
So for example, something that is Turing-complete- Computers these days are theoretically Turing-complete, but actually not, because they do not 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, it would be Turing-complete.
CW (00:09:28):
OK.
IZ (00:09:32):
Minecraft is Turing-complete because you can actually build this little robot inside Minecraft. 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.
(00:09:48):
"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.
EW (00:10:00):
So Turing-complete means that it is programmable?
IZ (00:10:07):
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 am never quite certain how to answer that question.
(00:10:27):
But morally speaking, it says, "If you asked me, 'Here is a program. Here is an input. Can you model this program, running on this input, in a Turing-complete context?' You can."
CW (00:10:38):
Does it say anything about what kinds of problems can be solved? Or is that a separate theory?
IZ (00:10:47):
I do not really know how to answer that question.
CW (00:10:50):
Yeah, sorry. I may not know what I am asking. So that is fair. <laugh>
EW (00:10:54):
Are there problems that are best solved with Turing-complete systems? I think about problems that cannot be solved with Turing-complete systems. Mostly chemical and biological, but maybe that is just not...
CW (00:11:07):
Yeah, I think it is a badly asked question on my part. Because it is a computer. So what kinds of problems can you solve with computers? Lots of them. <laugh> So yeah. Okay.
IZ (00:11:19):
It is really important to know what problems you can and cannot solve with a computer, because sometimes knowing that you cannot do something is more empowering than knowing that you can.
(00:11:29):
For example, here is something you can definitely solve with a computer, 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 of 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.
(00:11:53):
This can be solved with a computer, but we do not know of a way to find this in less than exponential time. So it is a very difficult problem to solve. The idea is that this is the kind of problem that if you are trying to solve with a computer, trying to get the best route is not a good idea. We can prove that it is not a good idea because it takes exponential time.
(00:12:25):
But once you know this, you can say, "Oh, well, that is fine. I am going to change my goal. Instead of trying to find the best route, I am going to look for a good enough route. Maybe one within 50% of being the best route, or something like that."
(00:12:45):
It is empowering knowing that you should not keep trying to look for the best one, because it is with modern technology an intractably difficult problem. You should instead be looking for a good approximation.
EW (00:13:00):
I would just like to give a virtual fist bump to everybody who is currently saying, "Simulated annealing!"
IZ (00:13:08):
For example.
EW (00:13:11):
And then go on and say, is that what "NP-complete" means? Or is that something else?
IZ (00:13:17):
It is something like what NP-complete means. Yes. Well, we do not know if P equals NP, so this is unknown, but I always felt that it was not. 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 is an NP non-exponentially.
CW (00:13:45):
Right.
IZ (00:13:45):
But right now, the best technology that we have says that this is exponential.
EW (00:13:53):
Okay.
CW (00:13:53):
So if you crack one NP non-polynomial problem, you crack them all.
IZ (00:13:58):
If you crack an NP-complete non-polynomial problem, you crack them all. Yes.
CW (00:14:02):
Right.
EW (00:14:04):
Which, if you could do that, you would be a wizard. That would be awesome for lots of things.
IZ (00:14:10):
And you win a million dollars.
CW (00:14:12):
All those salesmen would finally have optimal routes very quickly. Yeah.
EW (00:14:16):
<laugh>
IZ (00:14:18):
I think the issue with factoring prime numbers would be the bigger one.
CW (00:14:22):
Probably <laugh>. And dangerous.
EW (00:14:24):
There goes security.
IZ (00:14:25):
Factoring composite numbers into primes, not factoring prime numbers. That one is very easy.
CW (00:14:30):
Yes. Right. <laugh> Even I can do that.
EW (00:14:34):
Okay. So Turing-complete means it is computer-like, for those of us who need to have tiny definitions. NP-complete. Why "complete"? Means it is hard.
CW (00:14:48):
I do not remember what the complete means.
IZ (00:14:49):
The complete means that it is as hard as any other NP problem.
CW (00:14:54):
Ah, okay.
EW (00:14:54):
Okay.
IZ (00:14:54):
Because P problems are also in NP. So every problem- The question of what is 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.
CW (00:15:11):
Gotcha.
EW (00:15:12):
Okay.
CW (00:15:13):
Starting to remember. <laugh> It has been a while.
EW (00:15:16):
Okay. Cellular automata. Could you describe what those are?
IZ (00:15:25):
Okay. So cellular automata have- Well, they are like little cells- I always think of them in very similar to Conway's "Game of Life", which is a two dimensional cellular automaton. A cellular automaton is a bunch of cells sitting in some kind of geometric configuration. So the classics are a long line of cells, or a grid of cells of some sort.
(00:15:51):
But let us 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. At every stage the cell is either alive or dead. They can come back to life, it is fine.
(00:16:05):
So at every stage, the cell looks at the two cells on either side and looks at itself, and decides whether it is dead or alive in the next stage based on a very simple rule. The only information it is allowed to take is its current state and the state of its two neighbors.
EW (00:16:25):
I want to do Conway's Life before we go back to that one, because I know we are going to be talking about that some more. Conway's Game of Life is like you have described, except it is a grid, and you are looking at your four nearest neighbors.
IZ (00:16:37):
No, you are looking at your eight nearest neighbors.
EW (00:16:38):
Oh, you do diagonals, too.
IZ (00:16:40):
You look diagonally too. Did you know that there is an encyclopedia of constructs and Conway's Game of Life? It is still being added to, and it is amazing.
EW (00:16:52):
Because you can get little things that will shoot.
CW (00:16:54):
Flyers. What are the other things?
IZ (00:16:57):
There are blaster guns and spaceships and-
CW (00:17:00):
Right. There are little generators that shoot things. Right?
EW (00:17:01):
Yeah.
IZ (00:17:02):
Yeah. You can also- There are various theorems about- Suppose I have a spaceship that I wanted- Which is a pattern that travels across the plane. It does not 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 has moved in a certain direction. So that is why it is called a spaceship.
(00:17:24):
There are various people who try to construct a given spaceship with as few blaster guns as possible. It is just incredible to watch how clever these constructions are. You just have blasters set up in the plane, shooting blasts at each other, and then they create spaceships. So you have this infinite string of spaceships coming out of- Sometimes extremely complicated ones, just from a configuration of seven blasters.
EW (00:17:57):
All this is-
CW (00:17:57):
Okay, I have not seen factories built in Game of Life. That is really cool.
EW (00:18:03):
It is a grid. So let us say you have in code an array. That is your current...
CW (00:18:10):
State.
EW (00:18:10):
State. But each cell has its own state. It is either on or off.
IZ (00:18:15):
Yep.
EW (00:18:17):
Then it just looks at what is around it, to determine if it is going to die of loneliness or die of overcrowding.
IZ (00:18:24):
Or come back to life because it has just the right number of people near it. Or cells. Same thing.
EW (00:18:30):
Each one of these places, each one of these pixels acts independently. That is why they are called cells because they are each piece of code. This is one of those things where you can write very simple things, but get very complicated behaviors out of them when you start putting them together.
(00:18:49):
As I was thinking about that and thinking about the show, how are these different than neurons in machine learning? I know the math is all different, but is it?
IZ (00:19:04):
I actually do not think it is. I think it is just that when you have a more complicated object to work with, you can encode more more easily, but not necessarily more philosophically.
CW (00:19:17):
Yeah. Each cell is a little linear regression engine, I guess.
EW (00:19:21):
But what if we stopped thinking about them as linear regression?
CW (00:19:24):
Well, then you start- Then you- Steven Wolfram.
EW (00:19:26):
Oh, okay. Yeah, I did not read that book. I looked at buying it, but I did not read it. Okay. So back to Conway's Game of Life. Sorry, machine learning thing.
CW (00:19:35):
<laugh>
EW (00:19:35):
I think someday I will 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. 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.
IZ (00:20:02):
Yeah. So Rule 110 is one of these cellular automata that is just on a line. Again, each cell can look at itself and its two neighbors, and then it has to make a decision. It is called "Rule 110," because if you write out the eight possibilities of what that cell can see- 111 meaning they are all on. 110 meaning the right hand one is off, the cell itself is on, the left hand cell is on. And so on, down to 000, which is they are all off. And then you write out the next state of the cell underneath it.
(00:20:42):
That, and then read those eight bits as a binary number. That binary number is 110. I mean that in base 10. It is whenever 100 plus ten plus one. It is not six.
CW (00:20:59):
Gotcha.
IZ (00:20:59):
But you take the binary number, which is an eight digit binary number, and you read it in base 10, and then it is 110. So in fact, there is a Rule N for every N from zero to 255. So Rule 255 has all the cells-
EW (00:21:18):
Everybody lives!
IZ (00:21:18):
Just always-
EW (00:21:19):
Everybody lives all the time!
IZ (00:21:22):
And Rule 0 is everyone is dead all the time.
EW (00:21:25):
The Apocalypse Rule.
IZ (00:21:26):
Yes, the Apocalypse Rule. Exactly. And then there are various other Rules in between. Rule 110 turns out to be Turing-complete.
EW (00:21:36):
Okay. This rule for taking bits next to me suddenly now has the computing power of any computer.
IZ (00:21:49):
Yep. I think it is magic.
EW (00:21:51):
Okay. Good. Because that sounded kind of- We will go with magic and not bonkers, because who would say that?
IZ (00:22:04):
It is the great thing about- It is the thing in math that I love the most, that sometimes somebody tells you a result and you are like, "Absolutely not. No way. What are you smoking?" And then you work through it stage by stage, and you work through the proof and it is correct. Once you see the proof, you cannot argue with it anymore. It is just there.
(00:22:27):
This is actually one of the reasons right now there is 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 are writing it at a level where another expert in the field can understand it. And that leads to mistakes.
(00:22:58):
So the idea is, well, but if we also had a formalized proof of everything, the job of doing a proof would be writing it up in such a way that a computer could verify it. Then plugging it into the computer and the computer will say, "Yep, this is a correct proof," and you will know that you did something right.
EW (00:23:27):
How far has that gotten? Has it gotten all the way through Euclid?
IZ (00:23:31):
I am pretty sure. Right now the next big push is for Fermat's Last Theorem. So I am guessing. I do not actually know the state of Euclid. But I know they are working on Fermat's Last Theorem.
EW (00:23:45):
That has a ton of sub-theorems and things that it depends on, including probably all of Euclid.
IZ (00:23:53):
It is a huge project. I have a friend who was formalizing some proofs in algebraic topology- This is Reid Barton. He said this wonderful thing that I keep remembering, which is "Discussing with the computer what your proof says, is a really great way to figure out that you do not understand as much as you think you did."
CW (00:24:16):
<laugh>
EW (00:24:22):
<laugh> Yes. Is it easier to teach the computer or the students?
IZ (00:24:25):
Well, the computer only argues back when you are wrong, not when it is wrong.
EW (00:24:31):
<laugh> I see. We will not talk about the students then. One of the things about being a math prof or professional mathematician, is that you are proving things. As an engineer, that is very far outside my scope. My scope is applications. Why are proofs important?
IZ (00:24:56):
<silence>
EW (00:24:56):
Oh, great. Now she is not talking to me.
IZ (00:25:01):
No, you said it was okay to pause. I am pausing.
EW (00:25:05):
<laugh> I did. That is fair.
CW (00:25:08):
It is kind of a big question <laugh>. Why is breathing important? <laugh>
IZ (00:25:15):
Because you will die if you do not. That one is easier.
CW (00:25:20):
That one is easier. You are right <laugh>.
IZ (00:25:23):
<laugh> I am a mathematician, so I have trouble only giving one answer. So here is an answer. Historically, as mathematicians, we have not always had the same standard of proof that we have these days. It is actually a very modern invention, proofs of the standard at which we have now. It is only about 150 years old, which in math is very modern.
(00:25:47):
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 do not know if A happens. But you know that whenever A happens, B has to happen.
(00:26:17):
That kind of solidity is rare and beautiful and extremely reassuring, at least to me. Because there are many things in life you cannot control, but you can control proofs. At least once you have a proof. Before you have a proof, it is all chaos and horror.
CW (00:26:37):
<laugh>
IZ (00:26:38):
But after you have a proof, you at least know that you are not lying to yourself. Here is a classic example of something like this. Suppose I have a continuous function, so just a function from real numbers to real numbers whose graph I can draw without picking up my pencil.
(00:26:59):
Now I am going to take a sequence of these and they are going to approximate some other function. So they are getting closer and closer and closer to some other function. And I can ask, "Is that function continuous? Can I draw its graph with a pencil?" Intuitively you think, "Well of course, if you keep approximating it by continuous things, it is going to be continuous."
(00:27:24):
But the answer actually, "Nope. It is not. It will not 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 is going to rise very sharply until it gets to one, and then it is going to stay at one.
(00:27:40):
As that steepness gets steeper and steeper and steeper, you can approximate that vertical line as much as you want. But in the limit, you cannot have a vertical line on the graph of a function. You are going to have to jump, you are going to have to pick up the pencil.
EW (00:27:58):
The discontinuity.
IZ (00:28:05):
Yeah. So this intuitive thing that, "Well, of course it is going to work," it is fairly easy to construct an example where it does not. But then when you start working with more and more complicated objects, your intuition starts lying to you like this more and more.
(00:28:19):
So it is really important to know when your intuition is not lying. If I tell you something about topological spaces...
EW (00:28:33):
Which as far as I understand are all donuts.
IZ (00:28:35):
Yes, pretty much. That is a great way of visualizing. Donuts with different numbers of holes-
CW (00:28:39):
<laugh>
IZ (00:28:41):
In various configurations. It is a perfect way to visualize topological spaces. But you are already getting something slightly off, because donuts are smooth. A cube is also- The surface of a cube is also topological space, but it has these points at the vertices, where it is intrinsically pointed in a way that the donut never is.
(00:29:03):
If you are a tiny ant on the donut, the donut always looks smooth. But if you are a tiny ant on the cube, you can tell you are not on a donut because sometimes you get to these pointy points. And no matter how far you zoom in, they are always there.
CW (00:29:22):
Right. Those are those places that are not differentiable, right? So that is-
IZ (00:29:26):
Yeah.
CW (00:29:26):
Okay.
IZ (00:29:28):
Yeah. If you want me to be more technical, I can be more technical.
CW (00:29:32):
No. Our listeners will hate us. I am trying to be good.
IZ (00:29:35):
No, it is fine. I personally think of them as pointy points, but I am also not a geometer. But then in addition, I can tell you something so surprising that you will not believe me. And then the question becomes, "Can I convince you that it is actually true?"
(00:29:56):
Here is an example of something that a lot of people have trouble visualizing. Take all of three dimensional space. And I do not like the fact that there are 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.
(00:30:14):
So instead of now having different infinite directions wherever I go, I always end up in the same place when I go to infinity. The way you can think of this is it is the difference between a plane and a sphere. I have taken all of the edges of the plane and I have wrapped them up into a single point, and that is the North Pole, say. You are wrapping it around the sphere, and so now you have closed it up and it becomes a sphere.
(00:30:40):
If you do this for space, you get what is called the "three-dimensional sphere, S3." The statement is that I can decompose S3 into two donuts, which are linked, and which each have one hole. They are honest donuts. You can decompose S3 into two donuts, and they intersect at the surface of the donut.
(00:31:01):
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 am 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."
EW (00:31:19):
Excuse me, I have to go get some coffee.
IZ (00:31:20):
<laugh>
CW (00:31:23):
Okay, I am not arguing. I am trying to understand. What is the justification for the step where I can take all of the infinite points and merge them?
IZ (00:31:32):
So there are two kinds of spaces. Let us 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 is in fact compact, which is the actual important part.
EW (00:31:53):
Wait, wait. Is "compact" just mean that it is the smallest outside to inside thing- <laugh>
IZ (00:32:02):
No, compact means that it behaves like a finite object, in as much as a thing with infinitely many points in it can. So here is an example. If I am on the plane, I can walk in any direction and just keep going and I will never get anywhere. I can just keep going forever and ever.
EW (00:32:20):
Yeah, infinite.
IZ (00:32:22):
Infinite. But in a sphere, if I keep walking around the sphere, there is going to be some spot on the sphere that I keep coming back to. I will keep coming closer and closer and closer. Maybe I will never get to that specific point.
(00:32:33):
But there will be somewhere where you can put a post on the sphere- If you know how I am walking on the sphere, then you will be able to put a post on the sphere so that I will keep coming back to within it an arm's length of that post. I cannot get away from it. That is what compact means.
EW (00:32:49):
Okay.
IZ (00:32:51):
Technically it is what "sequentially compact" means. But anyway, for things like spheres, it does not matter which one you take.
EW (00:32:55):
<laugh>
CW (00:32:58):
Okay, we were talking about proofs. Okay, so this example of-
EW (00:33:03):
The sphere becomes the-
IZ (00:33:04):
This sphere becomes two torus.
CW (00:33:05):
S3 becomes two toruses.
IZ (00:33:08):
Two solid toruses. Yes. The justification is there is 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 is infinite. But in fact, quite often working in something that is infinite is just bad. We do not like to do it. We prefer things that are compact.
(00:33:32):
Adding this extra quote "point at infinity" is a very standard way of making space compact. So this is a very common object. It comes up all the time. So somehow cool decomposition theorems about it are a fairly standard thing to do.
CW (00:33:49):
Okay. I feel like I saw that somewhere in the past in physics, but I do not remember where the context was. But yes. Okay.
(00:33:54):
Elecia, you are...
EW (00:33:59):
I have the crazy eyes.
CW (00:33:59):
Yes. <laugh>
IZ (00:34:03):
<laugh> This is the thing that is so great about proofs. I can write down the formulas for this, and you can go over them. Even though you cannot visualize it, you can agree that mathematically it has to be true.
CW (00:34:15):
Each step follows another step logically and mathematically. Each of those is small enough to understand, and-
EW (00:34:22):
By someone familiar with the arts.
CW (00:34:23):
They lead to the inevitable conclusion, even if it is counterintuitive. Yeah.
IZ (00:34:27):
Yes. I love the counterintuitive ones more than anything else, because they are so great. I think the best referee report I have ever gotten on a paper, was a very negative report that said, "This paper cannot possibly be right, because K-theory does not work like that." I was so proud of it.
CW (00:34:47):
<laugh> And of course it was right?
IZ (00:34:48):
Oh, it was right. Yeah.
EW (00:34:53):
Okay. So you like bending brains. And you like the "reassuringness" of being sure you are right.
IZ (00:35:00):
Mm-hmm. And the two together is just the best thing ever.
EW (00:35:02):
You also like bending paper.
CW (00:35:03):
Wow. Very good segue.
IZ (00:35:03):
How was that?
EW (00:35:06):
Was that very good segue?
IZ (00:35:08):
Fantastic segue.
EW (00:35:08):
Which was perfect.
CW (00:35:09):
Definitely.
EW (00:35:12):
<laugh> What kind of origami do you usually do?
IZ (00:35:15):
It depends on whether I want to focus on something, and I have the time and space to focus on something. Or whether I am doing this in between running around with the kids. Or traveling. Or sitting in a conference when I am trying to pay attention to talks, and thus not too much to my origami.
EW (00:35:35):
Well, let us do the focused one. Because the other ones are toys and distracted.
IZ (00:35:42):
Yes.
EW (00:35:42):
Okay.
IZ (00:35:42):
Yeah. The ones where I can focus, I like super complex animals. I think they are just amazing and lots of fun. I think I have about ten super complex books. I have not done anywhere near everything from them. There are certain things that I have not quite been brave enough to.
(00:36:02):
Satoshi Kamiya has the Ancient Dragon, which is done on a 70 centimeter by 70 centimeter piece of paper. I desperately want to do it, but I have not been brave enough to do it yet. But that is what I tend to do when I can really sit down and focus.
(00:36:21):
So again, I like Satoshi Kamiya's Pegasus. I have done the Divine Dragon, Bahamut, that he has in his first book, four times largely because I have never done one that I felt completely satisfied with.
(00:36:37):
It is a very difficult 200 plus step fold. It produces this amazing dragon, which I think is from "Final Fantasy VII." It is standing on its hind legs and it has these giant wings. It is amazing. I love it. I want to make the most beautiful version of it that I can, and so I keep coming back to it.
(00:37:00):
I also, in a cuter version, found this origami model of the rat from "Ratatouille," that I have made four or five times now. I think it is adorable. It is 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.
(00:37:26):
Peter Engel also has this great kangaroo with a little baby kangaroo in this pouch. That is one of my favorites when I want to make something faster. As a very classic, John Montroll has his Stegosaurus, which is beautiful. Actually I have one right here in my office with me. Yeah.
EW (00:37:49):
I am using this for ideas, even though this is not really what I usually fold. I always find-
IZ (00:37:54):
What do you usually fold?
EW (00:37:56):
I really like curved creases.
IZ (00:37:57):
Ahh.
EW (00:38:01):
I do a little bit of pattern development for tessellations and corrugations. But I also like curved creases in animals. So I have jellyfish and an octopus and some snails, that use the curved creases to do a 3D effect that is smooth and biologically relatable.
IZ (00:38:23):
Oh, that is amazing. That is wonderful. I have never done curved creases because I do not like scoring.
EW (00:38:33):
You need your Silhouette system. Yeah.
IZ (00:38:36):
Yeah. I have always looked in- So amazing. I think it is incredibly beautiful, but I have never done any.
EW (00:38:46):
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- There are some patterns that are flat-lying
CW (00:38:59):
You do those tessellations, which-
EW (00:39:02):
I do like those.
CW (00:39:02):
Seem like they have thousands of steps, but they are-
EW (00:39:05):
They are repeating steps. Yeah.
CW (00:39:06):
Repeating. I see.
IZ (00:39:07):
What is your favorite tessellation?
EW (00:39:11):
Usually whichever one I folded last.
CW (00:39:15):
You like the ones with the negative- What is it?
EW (00:39:17):
Poisson ratios? Yeah. So anything in the Miura-ori folds.
IZ (00:39:21):
Mm-hmm.
EW (00:39:21):
I was working on trying to combine some Miura-ori style things with curves. I say that because looking at one I gave to Christopher <laugh>. That is all I can think about.
IZ (00:39:37):
That sounds really cool.
EW (00:39:40):
But it is not like Mooser's Train, which is box pleated and a thousand amazing detailed steps to get something.
IZ (00:39:52):
I have not done Mooser's Train. But I have the book, and I really want to.
EW (00:39:56):
Are you familiar with the Origami Simulator?
IZ (00:40:01):
No, I am not. I have no idea what that is.
EW (00:40:03):
It is so cool. It is origamisimulator.org. Amanda Ghassaei did it. 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.
(00:40:19):
Sometimes if you put in your own patterns, it will tell you that that is not foldable. Or it will just collapse in a billion little grid steps that did not succeed. Guess which one I like to do?
IZ (00:40:37):
That sounds really awesome. I have not looked at it before. I have done some tessellation, some designing of tessellations. But honestly, if I am going to spend hours on thinking through something, I would rather do something by Satoshi Kamiya, because I feel like it is very challenging. It is like "Wow, look at this amazing thing. Can I do it?"
(00:40:58):
With tessellations, which by the way, I fold all the time, they are just more of my conference / travel / kids folding.
EW (00:41:06):
Yeah. Mine too.
IZ (00:41:11):
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 do not reach for them.
EW (00:41:24):
But I would have called your NAND and NOR gates made out of origami to be on the tessellation spectrum, more than on-
IZ (00:41:34):
Oh, they definitely are.
EW (00:41:35):
Okay.
IZ (00:41:35):
Yeah. No, they definitely are. One of the things they were inspired by was origami tessellations. Just in my office, which is where I fold when I am really stuck on something, I have a pile of at least 20 tessellations that I have made within the past few months. I fold tessellations all the time. I think they are really awesome.
(00:42:02):
You cannot make a tessellation with 250 steps, because the piece of paper you would need is going to be too large.
CW (00:42:10):
<laugh>
EW (00:42:12):
Yeah. It depends on how you call the steps. But yes, because it is usually a repetition. If you are folding something 32 times horizontally, that is kind of one step.
IZ (00:42:28):
Yeah, that is exactly how I think about it. My favorite tessellation is probably Ilan Garibi's Pineapple.
EW (00:42:36):
Oh yeah, that is a nice one! A good way to take a big piece of paper and make it into a little piece of paper <laugh>.
IZ (00:42:43):
Yes, exactly.
CW (00:42:43):
I can do that. <laugh>
EW (00:42:46):
<laugh>
IZ (00:42:46):
It is a very challenging collapse also, especially because it is a two stage collapse. I have always wanted to make his multi-stage, three or four stage, pineapples too. And designing it! It is a brilliant feat of design. 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.
EW (00:43:15):
So you fold one, or maybe you set up a paper to fold them all. But after you fold one, it is a way of occupying your hands while your brain is doing something harder.
IZ (00:43:27):
Yes. Whereas something like the Divine Dragon, it is every step is different. Every step is asking you to do something else. Every step is making you think about what is going on with the paper in a different way.
EW (00:43:43):
Yeah. The only time I get really excited about the tessellations that are not curved, is when I look down and realize that I made a mistake, and it is really interesting.
CW (00:43:51):
<laugh>
IZ (00:43:51):
<laugh>
EW (00:43:51):
How do I do that again? <laugh> Okay, sorry.
IZ (00:43:58):
Sorry. Yeah, we got distracted by origami.
CW (00:44:00):
So you said you can make logic gates out of origami. I think that is where all this was headed, right? <laugh>
IZ (00:44:06):
Yes.
EW (00:44:06):
NAND and NOR. I feel like once you have those, you can get to Turing-complete because that is how computers are made.
IZ (00:44:16):
Pretty much. Yeah.
EW (00:44:18):
But you wrote a paper about Rule 110 and paper. Could you talk about that?
IZ (00:44:27):
Yeah. This is going to be a plug for Veritasium, because Veritasium is awesome. But I was watching the Veritasium video on Gödel's Incompleteness with my son and my husband.
(00:44:37):
Also just as a fun comment, they have a minor error in the first five minutes or so. My husband made me pause the video, to go on an explanation to my son about why it is wrong. I was like, "They are going to fix it. It is down the line, because I have seen it before." And my husband was like, "No, but that is not the point. It is wrong as it is stated now!"
CW (00:44:58):
<laugh> That is kind of on brand for being something about the Incompleteness Theorem. <laugh>
IZ (00:45:02):
Yes. Anyway, it was really great. It is a really wonderful video. It mentioned that the Game of Life is Turing-complete. 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 six times because it was amazing.
(00:45:23):
I have 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? I was sitting there going, "The Game of Life is really simple. I bet origami is harder."
(00:45:42):
I had seen results saying, "Flat folding origami is NP hard." And I thought, "Oh, well, if it is NP hard, it has got to be Turing-complete. It just has to. The NP hard paper did gates, and it has got to be Turing-complete. If you did an infinite sheet of paper."
(00:46:04):
So I wrote to Tom Hull, 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 is the paper. Thanks for writing." Instead he wrote back saying, "I do not know. That is a good question. Do you want to try to work on it?" So we did. We sat down and we worked on it.
(00:46:34):
Building gates is surprisingly hard. But the other thing, other papers have done similar things. But actually figuring out, okay, if you want to show something as 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.
CW (00:47:01):
Okay.
EW (00:47:01):
Rule 110.
IZ (00:47:05):
Rule 110. So in fact, originally I was trying to model the Game of Life. I thought, "Okay, the standard way to do transfer of information on a piece of paper is via pleats. So if you have a piece of paper, you can pleat it, just make a valley fold and then a mountain fold that are parallel, and you get a little pleat in the paper.
(00:47:28):
Depending on which direction you fold those, what order you choose, the paper will either point left or point right.
CW (00:47:34):
Okay.
IZ (00:47:37):
With that, you can transfer some information. Like "Which direction did you choose?" That is a bit of information. So that is the standard way to translate information down the page.
(00:47:49):
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.
EW (00:48:10):
<laugh>
IZ (00:48:10):
I tore a bunch of sheet of paper trying to get this to work, and I could not get it to work. Probably a better origami designer than I am would be able to do it, but I could not. So I went online and I looked for a list of things that are Turing-complete.
(00:48:26):
There is a list online of things that are Turing-complete, including "Magic: The Gathering" and Minecraft and a bunch of other things. I knew I was not going to be simulating Minecraft in origami.
CW (00:48:40):
<laugh>
IZ (00:48:40):
So that one, I just crossed off the list. But I was looking for the simplest things I could find. I saw this Rule 110, and I had no idea what it was. But I looked it up and I thought, "Okay. Three inputs. Do you know what you can do if you have three inputs and one output? That is only a four fold object that you need to make."
(00:49:01):
But even more than that, if you are 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. Sorry, when "above" I mean "before" it. A cell looks at itself and the two cells next to it.
(00:49:25):
So you have input from three different cells. You in the past, person to the left in the past, person to the right in the past. And then you have three different outputs. Yourself in the future, person on the left in the future, person on the right in the future. That is a six fold object.
(00:49:41):
I know how to make a six fold object. There are these things called "hexagonal twists" that take six pleats coming in a spiral, and twist them together so that they fold nicely. I was like, "Okay. Plus I know how to make a triangular 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."
EW (00:50:12):
The way you are talking about this makes the Conway's Game of Life even less promising, because it is not just eight in one out.
IZ (00:50:21):
Yeah. Exactly. It is nine in, really, because you also need to have your previous input.
EW (00:50:26):
And nine out?
IZ (00:50:28):
And nine out. Yeah. Also the output sort of needs to go vertically rather than horizontally. And paper is not 3D. I think Game of Life was a bad idea.
EW (00:50:39):
<laugh> I can see how you got there, but I am glad you found something simpler <laugh>.
IZ (00:50:44):
So that was the start. It was really just looking through this list of things that are Turing-complete. But once I was like, "Okay. The simplest kind of logic I can build on a hexagonal grid is gates. So can I build gates?"
(00:51:00):
Tom and I met, and we discussed. 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. Or AND and OR in various ways." We had several ways of writing it.
(00:51:15):
I was like, "Okay, so if we want to do this, we need to make gates." Tom was like, "Okay, but I do not quite know how to do that." And I was like, "Okay, but let us work on it." So we worked on it for a bit, and we came up with these gates.
(00:51:33):
We are slightly cheating with these gates, because the traditional flat folding origami mathematical question is, I am giving you a crease pattern. And the question is, "Will it fold flat?" That is the question.
EW (00:51:50):
Right.
IZ (00:51:50):
But I could not 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.
(00:52:05):
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 is fine. But you are not allowed to crease anywhere where there was not a pre-drawn crease.
(00:52:25):
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. I really hated the bi-directional folds, because they were just super-duper cheating. We are already cheating by adding optional folds. But now we are also adding bi-directional folds?
(00:52:47):
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. I was very unhappy with it. Tom, who is a practical and reasonable person, said, "It is okay. Let us see if we can do it with these, and then maybe we can discuss."
EW (00:53:11):
Optimize later. Yep.
IZ (00:53:13):
Optimize later. We could not quite figure out how to do it. Then I was at this very boring talk at a conference. I will not tell you whose talk it was, but I was in a very boring talk at a conference. I had my origami paper with me. I was planning on folding spread hexagons, which is an Eric Gjerde tessellation. It is one that nicely takes more attention. And I could sit there and pretend to be listening, while not listening at all.
(00:53:42):
I started folding this triangular grid that you need for it. Then I started thinking about this discussion that Tom and I had, and instead I started trying to fold a gate. 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 bi-directional creases.
(00:54:02):
I was so excited, and I wrote to Tom saying, "Hey, I managed to make a NAND gate." Actually, I managed to make an AND gate, but let us pretend I did not make that mistake. Tom was quite excited, and I sent him the crease pattern. He wrote back saying that he thinks it works, and he wanted to fiddle with it too.
(00:54:22):
The next day he sent me an OR gate. I was like, "Okay, well, we are in business. Once we have AND and OR, what else do we need? We need a NOT. NOTs have got to be easy." 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.
(00:54:49):
Then Tom was like, "Hey, Inna. I do not know if you know, but there is this classic mistake in origami computability stuff. Where the issue is that intersecting pleats can interfere with one another badly. They can shift the signal, and they can start interfering with one another from arbitrarily far away, and it is bad."
(00:55:15):
And I said, "We will not have the issue with things interfering from arbitrarily far away, because we are working on a grid. So you cannot have a crease coming up at a weird angle that is going to start interfering, and just getting more and more and more of them, because we are on a grid."
(00:55:31):
Tom was like, "Yes, that is true. That is a great point." I was very confused. I said, "How can intersecting things cause a problem? When I am doing tessellations, pleats intersect all the time, and it is never a problem." And Tom said, "No, but classically it is. Doing it without interfering with the signals is really hard."
(00:55:57):
I was like, "I do not think that is true, but let me try to figure it out." Tom was 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 am not sure you can do it." And I was like, "No, no, no. At 60 and 120 degrees, you definitely can do it. You have folded tessellations. It will be fine."
EW (00:56:21):
<laugh> It works fine.
IZ (00:56:24):
Tom was like, "Well, traditionally there are some problems with it." 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.
(00:56:34):
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.
CW (00:56:48):
<laugh> See, that is where it is really annoying. When your intuition is right, but it is really hard to prove it. <laugh>
IZ (00:56:55):
But what if something really weird goes wrong? I have definitely had things where my intuition is like, "Oh no, this will totally be right. And it is just wrong." So having the proof was very comforting. That was very intense.
(00:57:07):
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 NOT without bi-directional creases." I was like, "That is cool. Now we have got to get rid of them on everything else." And Tom was like, "No, it is fine." And I was like, "No, we have to get rid of them on everything else."
CW (00:57:29):
<laugh>
EW (00:57:30):
If you can get rid of them on the hardest one, you can get rid of them on all of them.
IZ (00:57:34):
Exactly! Plus the intersector did not 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 are no bi-directional creases needed. It will be fine." So we spent another week or so on it. We managed to get rid of the bi-directional creases, and I was very happy.
(00:57:55):
Then we had to go back to simulating Rule 110. Again, Tom was the practical one here. He said, "Let us do something simpler. Let us do a Sierpiński gasket." Which is really just checking whether two inputs are equal or not. If they are equal, you spit out zero. If they are not equal, you spit out one. That is what the mod 2 Sierpiński triangle is.
(00:58:22):
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. Then at every point you take 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. You keep going. You get the Sierpiński triangle going on forever. And it is fun.
(00:58:48):
So Tom was like, "Let us see if we can just do that. It will be a simpler crease pattern." And I was like, "You are right." I sat down and I planned it out. Again, if you look in the paper, you can see the layout of the Sierpiński gasket. Which takes I think 18 different gadgets. Because actually checking whether two signals are equal using gates, is surprisingly difficult. I had never thought about it, but it is.
(00:59:19):
In addition, you need to do this complicated thing, where you need to reflect a signal. That was the thing that actually took me the longest to figure out how to do. What you want to do, to check whether two signals are equal-
(00:59:36):
So suppose that you have two signals, A and B. 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. The other way you look at NOT A and B, and again, this tells you whether A is false and B is true. So those are the two cases when you can pick out that they are different.
(01:00:15):
Then you look at those two signals, and if either 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.
CW (01:00:41):
Okay.
IZ (01:00:44):
So you have one signal which is A, and you have one signal which is B. Now you need to split them, compare them in different ways, and recombine. And when you are doing this with origami, your signals have a direction. It is not like with wires where you can loop things around however you like. Your signals are straight lines.
(01:01:04):
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 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 recombine them.
(01:01:27):
So you want to be able to reflect a signal. One of these signals is sort of going towards your computation bit. The other one is going away, and you need to be able to reflect it back into the center. That was actually the hardest part of the whole thing. How do I reflect the signal?
EW (01:01:47):
Tease and getting the signal where you want it to go?
CW (01:01:51):
It sounds like you can build a computer out of waves.
IZ (01:01:55):
Oh, that would be really cool.
CW (01:01:56):
Right. So you are talking about these signals, and they are being reflected in folds that are- I presume they are moving some way, right? You are refolding. So-
IZ (01:02:06):
Oh, no, no. The idea is you are never refolding.
CW (01:02:07):
Okay.
IZ (01:02:07):
The question that you end up asking is, "Will this fold flat ever, or not?"
CW (01:02:12):
Okay. Right. Got it. Okay. So I am thinking about this somewhat the wrong way.
EW (01:02:17):
Yeah, we are not moving the paper.
CW (01:02:18):
Yeah. Okay.
EW (01:02:19):
We are folding all the things flat, and it is the initial conditions.
CW (01:02:22):
Gotcha. Okay. So it is a single computation, is the fold.
IZ (01:02:27):
Yes.
CW (01:02:27):
The complete set of folds. Okay, cool. Got it.
EW (01:02:32):
How many of these do you have in your office?
IZ (01:02:37):
Gates? I have a lot. I tend to-
EW (01:02:40):
What about a full Rule 110?
IZ (01:02:43):
I have zero-
EW (01:02:45):
Really?
IZ (01:02:45):
Rule 110s. I even have zero Sierpiński gaskets. Largely because I tried to fold it from one very large sheet of paper, that I folded a 128 grid on. And it is really hard to fold, it turns out, because there is so little regularity to what is going on. Usually on a tessellation, I start in the middle, or I start on one of the edges. And there is enough regularity to what is going on, that I feel like I have some control over what is going on.
(01:03:17):
With this large paper, I felt like I just had no control over anything. At some point, the plan is to sit down and sort of draw on the paper exactly where I am planning to put everything-
EW (01:03:27):
Oh, yeah.
IZ (01:03:27):
And then try it again. But usually I do not plan like that. Usually I just sit and start folding. With this particular thing, it was just not possible.
EW (01:03:37):
I have a Cricut. I was looking at this and thinking I could probably have it precrease for me. Then I could color in, using the same colors you have in your paper.
IZ (01:03:51):
Mmm. That would be awesome.
EW (01:03:52):
There is no way I could just remember.
IZ (01:04:00):
Mm-hmm. But then, a couple of weeks ago I was looking at this pattern again. I was like, "I could do this modularly. And I know how to do it modularly."
(01:04:08):
So my current plan right now is- I have these hexagons that I cut on my Silhouette. The plan is to fold modular bits of this pattern. Put them all together, and attach them to each other with paperclips, and see if it will work that way. Then it will look like a circuit, and it will be great.
EW (01:04:29):
That would look really cool.
IZ (01:04:33):
So that is 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. Then somebody wants to play around with one, so I make another one. Then I tend to give those away, and so on and so forth.
EW (01:04:52):
You could use magnets instead of paperclips too. Then you could just pick them up, and put them around in a different NAND NOR configuration.
IZ (01:05:00):
Oh, that would be really cool. Do you know the game "Turing Tumble"?
EW (01:05:07):
No.
IZ (01:05:09):
It is this amazing game that- My kids loved it. But it is pretty much-
EW (01:05:18):
Marble-powered computers?
IZ (01:05:20):
Yes! It is marble-powered computers. Also all of the pieces work in this extremely satisfying, beautifully engineered way. So it all clicks together in just this amazing way.
(01:05:30):
It is pretty much programming problems. It will tell you, "Oh, you have these limitations. Like you have to use these parts, and you are 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 red marble, et cetera, et cetera. How do you do it?"
EW (01:05:47):
<laugh>
IZ (01:05:48):
The point is you could just set up the parts. Then you hit the lever to make it go. And it goes clickety, clickety, clickety, clickety, clickety. It is beautiful. I think would be really amazing to make an origami gates version of this. But I am not a game designer, especially not one as brilliant as the ones who made that game. So this is on my wishlist for the world.
EW (01:06:15):
I had plans this weekend.
CW (01:06:17):
Did you? <laugh>
EW (01:06:18):
I did. They involved origami, but not this.
CW (01:06:20):
<laugh>
IZ (01:06:20):
<laugh>
EW (01:06:20):
All right, well this looks really cool. Do you have SVGs of the patterns?
IZ (01:06:32):
I do. Actually, they are entirely made in TikZ. So I can send you the TikZ code. Both the Sierpiński triangle one and the Rule 110 one are just code in TikZ, and I am happy to send it to you. It is actually also available in Archive, because you can download the TeX code and it is just in there.
EW (01:06:52):
What is TikZ?
IZ (01:06:54):
TikZ is a graphical package for LaTeX. So it is just like-
EW (01:06:59):
This just keeps getting worse and worse.
CW (01:07:01):
Remember, she has to write actual academic papers.
EW (01:07:02):
<laugh>
IZ (01:07:02):
<laugh>
CW (01:07:02):
She cannot just put stuff on GitHub, and call it a day.
EW (01:07:08):
How many Python Colabs do I have for my origami? Quite a few.
IZ (01:07:20):
Let me tell you something funny. At the Joint Math Meetings, which is the largest math conference in the US. I do not know about the world, but it is definitely the largest math conference in the US. It happens yearly in January somewhere. This year it was in San Francisco.
(01:07:32):
They had a session on serious recreational mathematics. It was one of the most amazing mathematical sessions I have ever been to, and I hope they have more. It was just amazing. Tom Hull, my collaborator, spoke about this paper.
(01:07:50):
Prior to his talk there were these amazing videos of giant sheets of plastic folding up into bus stops, and these amazing simulations of fonts shifting into one another, I was very impressed by. But there was a lot of computer science people there. I do not know if it was just not impressive or what, but I thought they were amazing.
CW (01:08:18):
<laugh>
IZ (01:08:20):
And then my collaborator showed them this picture of the Rule 110 cell. He said, "And this was made by hand in TikZ." There was a gasp through the room, like an audible gasp.
EW (01:08:34):
<laugh>
IZ (01:08:36):
This is not- I do not know whether that is 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 tell it the coordinates of gates, and it will generate everything on its own."
(01:08:51):
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."
CW (01:09:02):
<laugh> Depends on how many more times you want to do it.
IZ (01:09:04):
Exactly. So this is the question. Am I ever going to do it again? Maybe. So maybe I should have done an automated thing. But everything in this paper is done by hand. In fact, if you download the LaTeX code, you can see how it is all done.
EW (01:09:22):
Okay. Well, I may need help with that, but you will be the second person I ask for help.
IZ (01:09:28):
<laugh> Excellent.
EW (01:09:29):
Christopher looks away, knowing he is the first.
IZ (01:09:30):
<laugh>
CW (01:09:32):
Do not make me do math. It has been too long.
EW (01:09:34):
I will make you do LaTeX.
CW (01:09:36):
No, do not make me do LaTeX <laugh>. It has been even longer.
IZ (01:09:38):
<laugh> That is almost worse.
CW (01:09:41):
I was really good at it, at one point. In the nineties.
EW (01:09:43):
<laugh>
IZ (01:09:46):
My website is still from the nineties.
EW (01:09:50):
This has been very interesting. Now I have so many more ideas from cellular automata and neural networks, to new folding ideas, to game design with origami. I am just-
CW (01:10:07):
I think you should pick one. <laugh>
EW (01:10:08):
My brain is fizzy. Do you have any thoughts you would like to leave us with, Inna?
IZ (01:10:15):
There is a comment I sometimes get from serious mathematicians, who do not do things like origami math in addition to other math, which is "Why would you do this? What is the point? Who cares?"
(01:10:31):
The point is that it is awesome and cool, and that is 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 are doing it.
CW (01:10:48):
There are always applications later, that somebody else can figure out.
IZ (01:10:53):
It is just cool.
EW (01:10:53):
Oh, my God.
CW (01:10:53):
And it is just cool. So do not worry about it.
EW (01:10:56):
All the ideas that I have. The rigid foldability, and then we can go on to flex circuits in this. Oh, my God. There are so many-
CW (01:11:03):
I am on board with stop worrying about why.
IZ (01:11:06):
Yeah. That would be so cool.
EW (01:11:09):
Our guest has been Inna Zakharevich, Professor of Mathematics at Cornell University.
CW (01:11:15):
Thanks, Inna.
IZ (01:11:17):
Thank you so much.
EW (01:11:19):
Thank you to Christopher for producing and co-hosting. Thank you to our supporters on Patreon. Thank you to Memfault for sponsoring this week's show. You can always contact us at show@embedded.fm or hit the contact link on embedded.fm. Or you can go to Amazon and buy my book "Making Embedded Systems, Second Edition."
(01:11:38):
And now I have a quote to leave you with, from Alan Turing. "Machines take me by surprise with great frequency."