Cristopher Moore: uncertainty

Transcript context

…110, right? My bad. But but, you know, I I know you you've done studied, you know, like the the 3 body problem. Right? So so you you you do this this computation step by step, and there are no analytical shortcuts. Right? You just you just have to do this this wide ranging divergent, you know, and then and then you find something. And and that's amazing. You you've hit this stepping stone, but that there was no shortcut to get that. Right. Or like a chaotic dynamical system where there's no closed form solution if you want to know the state it will be in at some future time, you can't just plug t into some formula. You have to numerically integrate it, and, you have to do the work. You have to you can't skip over its intervening history. And so, yeah, I mean, cellular automata are a great playground for this. There are some, the for the geeks, like rule 1 50, which are kind of linear, and, they're like linear mod 2 or something. And so if you want to if if I give you the initial state and you want to know the state at some future time, you can almost just plug it into a formula. You can you can create that future state with much less computation than it would take you to actually simulate. And then there are others where we strongly believe that you have to go step by step, the irreducibility, as you said, that Wolfram likes. 1 of the 1 of the fascinating things about this is that our only techniques for proving that prediction is hard, that you have to do the simulation, is to build a computer out of the thing. So, you know, what happened with rule 1 10 was that Wolfram observed all these cool particles and thought, gee, you know, these particles are doing all these cool collisions, almost like chemistry, or almost like almost like reading and writing symbols on a Turing machine's tape. And so, and then Matt Cook, came along and, you know, with Wolfram, completed this proof and proved Wolfram's conjecture. And, then my friend Damien Woods came along and and did it more efficiently and so on. So this is a lot like NP completeness. Right? We prove that problems are hard because they have some kind of universal ability to encode or express other problems. Therefore, if they were easy, these other problems would be easy too. And a funny thing though is there are a lot of systems where we don't know how to build a computer in them, but they still look really irreducible. They're still doing all kinds of stuff that looks really nonlinear, and it really doesn't look like you could jump forward in time. But the stuff is so uncontrolled that we don't see how to build a computer out of it, so we can't prove that we can't skip over the simulation. So imagine that you were walking around in a world imagine that you were thinking about computational complexity several thousands of years ago, which I guess you could have done, and maybe in some philosophical sense some people did. But suppose you don't yet have, like, wires or pipes or, in general, things that can transmit some information, a bit or whatever, very cleanly from here to there. And you didn't have little gates that take these clean wires and then produce something else and send it out along another wire. Suppose you just had this kind of what a friend of mine calls lava of just this chaotic stuff going all over the place. Or, you know, like, looking at the, you know, the the flow of plasma in the sun. Right? you just had this kind of what a friend of mine calls lava of just this chaotic stuff going all over the place. Or, you know, like, looking at the, you know, the the flow of plasma in the sun. Right? These amazing videos we have now from these solar telescopes, you see things briefly forming and then breaking apart, and it's very chaotic. It's sort of like it's like the planet Solaris or something. Right? There's the what you don't see is stuff that's out of which you could say, oh, that is a nice controlled building block. I could use that to store a bit that I could then write to later or read from later or, like, combine to. So some cellular automata have this kind of very chaotic, very nonlinear looking structure. But what they don't have that we know of are these nice particles that we can use to transmit and modify information and simulate a Turing machine or whatever. And I wonder if a lot of natural systems are in this weird middle ground. Right? You can build hydrodynamic computers if you have pipes and valves. And before transistors were coming along, people were trying to build microfluidic computers. Right? There's some wonderful alternate history in which we don't have transistors, and what we have is microfluidics everywhere, and that would be fun to think about. It's a little bit like the difference engine, the stuff with right, Bruce Sterling and William Gibson have a novel about that, where the kind of Babbage succeeded in building these mechanical computers, and that's the technology we have. But you but can you build a computer just out of water? Just the flows of water? Maybe, you know, just out of the Navier Stokes equations, using little flux donuts to travel from here to there. Maybe. And some people say yes. And but it seems harder because you things are not channeled. Yes. So there's a difference between the complexity of a system and whether we can get it to do the computations we want it to do. Right? It might be doing very complicated computations internally that are indigenous to its own dynamics. That doesn't mean that we could say, oh, good. Now I can use it to build a computer. Formally, we know that there are problems which are undecidable, but which are not Turing complete in the sense that if I gave you a box that solves this problem, an oracle for this problem, that you could then solve the halting problem. So they're undecidable, but not because the halting problem can be reduced to them. Similarly, we know that if p and m p are different, which we believe, the the academic we, almost everyone I know believes that, not everyone. But if p and n p are different, then there are problems in the middle ground which are outside p. They cannot be solved in polynomial time. They cannot be solved efficiently, and yet they're not NP complete. They don't have the ability to capture other things. And, you know but the annoying thing is the only way we can prove that a problem is hard is by showing that it is complete, essentially by building a computer out of it.…

Stored transcript either side of the excerpt. The highlighted words are the published quote; the surrounding text is unedited source, never generated.