Transcription
When I was speaking to Wolfram about that, Stephen Wolfram, he said that he's not a fan of category theory because he believes it circumvents computational irreducibility. I said, why? He said, well, because you go from A to B, yes, then you can go from B to C, but then you also have an arrow that goes directly from A to C. But when I was thinking about it, that's only the case if you think that each mapping takes a time step. But when I look at category theory, I don't see it as any time step. At least I don't. I see it as just this timeless creation. So please tell me your thoughts.
Right. Okay. Well, so I'm in the fortunate position of having written quite a long paper on exactly this problem. So there's a paper that I wrote back in 2022 called “A Functorial Perspective on Multicomputational Irreducibility,” which is all about exactly this idea that, yeah, so as you say, category theory, as it's ordinarily conceived, is just a kind of algebraic theory that has no notion of, there's nothing computational about it, right? There's no notion of time step. There's no statement made about, you know, what's the computational complexity of any given morphism. But then an obvious question is, well, okay, is there a version of category theory which does care about those things, a kind of resource version or some version where individual morphisms are kind of tagged with computational complexity information? And it turns out the answer is yes, and it has some very nice connections to not just categorical quantum mechanics, but also things like functorial quantum field theory. But also, it gives you a new... I think Stephen is wrong in that statement that it doesn't care about computational irreducibility, because actually it gives you a very clean way of thinking about computational irreducibility.
So what I mean by that is, so computational irreducibility, this idea that there are some computations that you kind of can't shortcut in some fundamental sense. As far as I know, I was the first person to actually give a formal definition of that in a paper back in 2018 or something.
Sorry, a formal definition of computational irreducibility?
Of computational irreducibility. Nothing very profound, but just essentially you say, I've got some Turing machine that maps me from this state to that state. Does there exist a Turing machine of the same signature that gets me to the same output state with fewer applications of the transition function? And so, I mean, I needed that for another result that I was proving. But having looked in the literature, I'm not aware of anyone previously who'd formalized that definition.
Sorry, I don't mean to cut you off. So please just remember where you are. Okay, because it's my understanding that Wolfram said that rule 30, something like that—maybe you would recall it more vividly because it's in his book—rule 30 is computationally irreducible. I've always wondered, how do you prove that? Now, I imagine that he proved it, or maybe it's one of those Wolfram proofs, so proofs to himself. But in order for him to prove it, even to himself, he would have had to have a definition of it.
Right, okay, so there's an important point that, so rule 30 is not proved to be computationally irreducible and in fact there's a prize. So if you go to, I think it's rule30prize.org, I'm ostensibly on the prize committee. This is a prize that Wolfram put out back in 2018. There's actually three prizes, none of which have been claimed, each one is ten thousand dollars, and one of which is prove that rule 30 is computationally irreducible. And so yeah, it's unproven. And in fact, there's really only one, up to some notion of equivalence, there's really only one of the elementary cellular automata in NKS that's been proven to be computationally irreducible in any realistic sense, and that's rule 110. And that was proved by showing that it's capable of doing universal computation, that it's a Turing rule. And so intuitively you can kind of say, well, if it's Turing-complete, then questions about termination are going to be undecidable and therefore it has to be irreducible. But it's a kind of slightly hand-wavy thing. But yeah, so in a way it's an interesting question. Can you prove that something is computationally irreducible without proving that it's universal? And of course, as you say, for that, you would need a formal definition of irreducibility.
Okay. And now going back to your paper on functoriality and computational irreducibility, you were able to formalize this.
Yes. Sorry. Yes. So what I was saying was, yeah, so there was this existing formal definition of computational irreducibility. But I then realized that if you think about it from a category theoretic standpoint, there's actually a much nicer definition, a much less kind of ad hoc definition, which is as follows. So imagine a version of category theory where your morphisms, as I say, are tagged with computational complexity information. So each morphism has a little integer associated to it. So, you know, you fix some model of computation, you fix Turing machines, and you say, each morphism I'm going to tag with an integer that tells me how many operations was needed to compute this object from that object. In other words, how many applications of the partial transition, of the transition function of the Turing machine did I need to apply? So now what you have, so now if I compose two of those morphisms together, I get some composite. And that composite is also going to have some computational complexity information. And that computational complexity information, it's going to satisfy some version of the triangle inequality, right? So if it takes some number of steps to go from X to Y and some number of steps to go from Y to Z, I can't go from X to Z in fewer computational steps than it would have taken to go from X to Y or from Y to Z. So it's going to at least satisfy the axioms of something like a metric space. There's some kind of triangle inequality there. But then you could consider the case where the complexities are just additive, right? Where, you know, to get from X to Z, it takes the same number of steps as it takes to go from X to Y plus the number of steps it takes to go from Y to Z. And that's precisely the case where the computation is irreducible, right? Because it's saying you can't shortcut the process of going from X to Z. Which then means you could define the reducibility, the case of computational reducibility, as being the case where the algebra of complexities is sub-additive under the operation of morphism composition. And there's a way that you can formulate this. So you take your initial category, and you take a category whose objects are essentially integers and discrete intervals between integers, and then you have a functor that maps each object in one category to an object in another, each morphism in one to a morphism of the other. And then the composition operation in the second category is just discrete unions of these intervals. And then you can ask whether the, you know, essentially whether the cardinality of those intervals is discretely additive or discretely sub-additive under morphism composition. And that gives you a way of formalizing computational irreducibility. And the really lovely thing about that is that not only can you then measure irreducibility and reducibility in terms of deformation of this functor, but it also generalizes to the case of multi-way systems. You can formalize notions of multi-computational irreducibility by essentially just equipping these categories with a monoidal structure, with a tensor product structure.
So my understanding of computational irreducibility is either that a system has it or it doesn't, but it sounds like you're able to formulate an index so that this system is more irreducible than another, like you can actually give a degree to it.
Exactly, exactly. So, yeah, so there's a kind of, there's a limit case where it's exactly additive, and anything that's less than that, you know, where the complexities are exactly additive, that's kind of maximally irreducible. But anything less than that is sort of partially reducible, but not necessarily fully reducible.
Now are there any interesting cases of something that is completely reducible, like has zero on the index of computational irreducibility? Is there anything interesting?
Even trivial is interesting, actually. Yes, I mean, well, okay, so any computation that doesn't change your data structure, that's just a repetition of the identity operation is going to have that property. I'm not sure I can necessarily prove this. I don't think there are any examples other than that. I think any example other than that must have at least some minimal amount of irreducibility. But yes, I mean, this also gets into a bigger question that actually relates to some things I'm working on at the moment, which is exactly how you equivalence objects in this kind of perspective, right? Because even to say it's a trivial case, right, where I'm just applying some identity operation, I'm getting the same object. You have to have some way of saying that it is the same object. And that's actually, I mean, that sounds like a simple thing, but it's actually quite a philosophically thorny issue, right? Because you know in a very simple case you could say, well, okay, so sorry, first thing to say is everything we're talking about at the moment, this is all internal to this category, which in the paper I call comp, this category whose objects are in a sense elementary data structures and whose morphisms are, or the morphisms that generate, that freely generate this category, are elementary computations. And so the collection of all morphisms that you get from compositions are essentially the class of all possible programs. So within this category, when two objects are equivalent, and therefore when two programs are equivalent, is a fairly non-trivial thing, right? So you can imagine having a data structure where nothing substantively changes, but you've just got like a time step or something that goes up every time you apply an operation. So it just increments from one, two, three, four. So in that case, you're never going to have equivalences. Every time you apply an operation, even if the operation morally does nothing, it's going to be a different object. So even that would show up as being somehow irreducible. But there are also less trivial cases of that, like with hypergraphs, right? So with hypergraphs, you have to determine equivalence, you have to have some notion of hypergraph isomorphism. And that's a complicated thing even to define, let alone to formalize algorithmically. And so you quickly realize that these notions, you can't really separate these notions of reducibility and irreducibility from these notions of equivalencing. And that somehow it's all deeply related to why, what data structures do you kind of define as being equivalent or equivalent up to natural isomorphism or whatever? And that's really quite a difficult problem that relates to definitions of things like observers in these physical systems, right? If you have someone who is embedded in one of these data structures, what do they see as equivalent? Which might be very different to what a kind of God's eye perspective views as being equivalent from the outside.
So are there closed timelike curves in Wolfram's physics project? Sorry, his project?
No, we can say “Wolfram physics.” I mean, that's how it's known, right? No, so, yeah, that's a really good question, right? Because, you know, in a way, it's very easy to say no, because we can just, we could do that trick that I just described where, you know, you just tag everything with a time step number. And then of course, you know, you, even if the hypergraph is the same, the time step is different. So you, there's no equivalency. You don't, in the multi-way system or the causal graph, you never see a cycle, but that's somehow cheating, right? And when people ask about CTCs, what they care about is not this very nerdy criterion of, oh, do you actually get exactly equivalent data structures? What they care about is…
Nerdy criterion seems to define this entire conversation up until this point.
Well yes, I suppose. You take two people with math backgrounds and get them to discuss stuff. Yeah, exactly. That's going to happen, right? But yeah, so yeah, what they care about, people who care about time travel. Right. What one cares about is, yeah, exactly, is time travel and causality violations and things, which don't necessarily care about your equivalency or care about them, care about it in a slightly different way. My short answer is I don't know, because I think we can't, my personal feeling is we are not yet at this level of maturity where we can even pose that question precisely for the following reason, right? So even defining a notion of causality is complicated. So in most of what we've done in that project, in derivations of things like the Einstein equations and so on, we've used what on the surface appears like a very natural definition of causality for hypergraph rewriting. So you have two rewrites. Each one is going to ingest some number of hyperedges. It's going to output some other number of hyperedges. Those hyperedges have some identifier. And then you can ask, okay, did this future event ingest edges that were produced in the output of this past event? And so if it did, then the future event couldn't have happened unless the past event had previously happened. And so we say that they're causally related. So somehow if the output set of one has a non-empty intersection with the input set of another, we say that they're causally related. That seems like a perfectly sensible definition, except it requires, it has exactly the problem we've been discussing, right? It requires having an identifier for each of the hyperedges. You need to be able to say this hyperedge that this event ingested is the same as this hyperedge that the other event output. But if they're just hyperedges, they're just structural data, there's no canonical choice of universal identifier, of UUID. And so what that means is you can have these degenerate trivial cases where, for instance, you have an event that ingests a hyperedge, changes its UUID, but doesn't actually change anything structurally. The graph is still the same. Nothing has actually changed, interestingly, but the identifier is different. But now any event in the future that uses that edge is going to register as being causally related to this other event that didn't do anything, right? And so you have a bunch of these spurious causal relations. So it's clear that that definition of causality isn't quite right. And so what's really needed is some definition of causality that isn't subject to this problem, but it's very unclear what that is. And I worked a little bit on trying to formalize that using, by essentially by recursively identifying hyperedges based on their complete causal history. So the identifiers are not chosen arbitrarily as random integers or something, but instead each hyperedge encodes in a slightly blockchain way a directed acyclic graph representation of its complete causal history. And so then two hyperedges are treated as the same if and only if they have the same history of causal relationships in the rewriting system. And that's somewhat better, but again, is quite complicated to reason about. And as I say, it's all deeply related to this question of what data structures do you ultimately treat as being equivalent, which is really an observer-dependent thing. It depends on the computational sophistication of the person or entity who is trying to decode what the system is doing. It's not the kind of inherent property of the system itself.
So what do you make of observer theory, which is a recent large blog post by Stephen? And a theory, well, an outlook.
So what do you make of it? Yeah, so Observer Theory really has, it's a rebranding of this thing that's been a feature of the physics project since before we started it, right? So this idea that, yes, exactly, that you cannot sort of consider a computational system independent of the observer that is interpreting its results. And somehow both the computational sophistication of the observer and the computational sophistication of the system have to be factored into that description somehow. So in a way, it's a very natural, that idea, which is really the prelude to this work we did on quantum foundations and other things in the context of the physics project. I like to think of it as a kind of natural extension of a bunch of stuff that happened in 20th century physics, right? Because, of course, this is not how these things were viewed at the time. But both general relativity and quantum mechanics can, in some sense, be thought of as being theories that you arrive at by being more realistic about what the observer is capable of. Right? So if you say, you know, okay, traditional, a lot of traditional scientific models made this assumption that the observer was kind of infinitely far removed from the system they were observing, that they were, they somehow, you know, they were these kind of omnipotent entities, they didn't have any influence over the systems, they weren't constrained by the same laws. But if you then say, okay, well, maybe the observer has some limitations, maybe they can't travel faster than light, right? What does that imply? Well, in some, if you follow the right chain of logical deduction, what that implies is general covariance and therefore general relativity. That as soon as you have observers who can't travel faster than light, they don't necessarily agree on the ordering of spacelike separated events, and suddenly you get general relativity. Equivalently, if you have observers who are constrained by the same physical laws of the systems that they're observing, then what that means is, you know, if you try and measure some property of a system, what happens when you measure it? Well, you have to have some interaction with it, you have to kind of poke it somehow. And the poke that you receive back is going to be equal in magnitude to the poke that you gave to the system. And so anytime you try and measure some quantity, there's a minimum amount that you have to disturb it. And again, if you kind of follow that chain of reasoning to its logical conclusion, you get at least the kind of Heisenberg picture of quantum mechanics. So in a way, both general relativity and quantum mechanics are, as I say, ways of becoming more realistic about what observers are capable of, and ways of coming to terms with the fact that observers are constrained by the same physical laws as the systems that they observe. So observer theory, which, I mean, I don't think it's yet a theory, so I'm not sure it's, you know, no, I'm not, I'm sure, I'm hugely fond of the terminology, but I mean it as a conceptual idea is really just the kind of computational instantiation of that. And you know, so my feeling, okay, you mentioned before this very interesting thing about geometry, that somehow, you know, you have this freedom of, do you choose to vary curvature, do you choose to vary torsion, do you choose to vary non-metricity? My feeling is that there's a similar free parameter that exists in our scientific models with regards to the role of the observer. And this is again maybe a point of philosophical departure from between me and Stephen is, so you have these kind of, you can imagine these two extreme cases, right? You can imagine the case where all you care about is the computation that the system is doing. So you're just building up some structure from, you know, from bottom-up rules, and so the observer, so to speak, is just some trivial object that's seeing the data structure, and all of the kind of computational burden is being shouldered by the system itself. And that's the way that the physics project is often presented, right? You just have a hypergraph and it's doing its thing and we perform analyses on it. That's one extreme. There's another extreme where you could say, well, maybe the system itself is trivial. The computation it's doing is essentially trivial. And all of the sophistication, all the computational burden is shouldered by the observer. So the case of that would be what Stephen refers to as the Ruliad, which is really just this what I was describing earlier, this kind of category of, you know, all possible elementary data structures and all possible computations. And so in that picture, I mean, that's a kind of, that's an object that minimizes algorithmic complexity, right? It minimizes Kolmogorov complexity, the, you know, the set of all possible computations has the same algorithmic complexity as the set of no computations, just purely for information theoretic reasons. And so in that case, the actual computation that generates it is trivial. It's trivial to specify. But in order to get a particular computational path, or in order to restrict down to a particular multiway system, you have to have an observer, some generalized observer, who is making equivalences between different paths, and the sophistication of that observer can be arbitrarily high. And so you have these two extreme cases. One case where the observer is trivial, all the computation is being done by the system. Another case where the system is trivial, all the computation is being done by the observer. And my argument is these two cases, I mean, there's no observational way of distinguishing between them. And in fact, there's the whole interstitial space in the middle where you have some of the burden being shouldered by the system, some of the burden being shouldered by the observer. These are not really things that we can observationally distinguish. And so in a sense, it's a genuinely free parameter in how we construct our models. And I would even go so far as to say that I think, in some sense, this argument that occurred in early European philosophy between the kind of empiricists and the rationalists, between people like Locke and Hume on the kind of empiricist side, and people like Descartes and Bishop Berkeley and so on on the rationalist side. This is really the modern version of that same argument. The empiricist saying, we need to get the observer out of the picture as much as possible and just describe the systems. The rationalist saying, no, no, what matters is the internal representation of the world and the external reality is somehow some secondary emergent phenomenon. That's exactly this case. In a sense, the two extremes of maximal algorithmic complexity of the observer versus maximal algorithmic complexity of the system.
Hi, everyone. Hope you're enjoying today's episode. If you're hungry for deeper dives into physics, AI, consciousness, philosophy, along with my personal reflections, you'll find it all on my Substack. Subscribers get first access to new episodes, new posts as well, behind the scenes insights, and the chance to be a part of a thriving community of like-minded pilgrimers. By joining, you'll directly be supporting my work and helping keep these conversations at the cutting edge. So click the link on screen here. Hit subscribe and let's keep pushing the boundaries of knowledge together. Thank you and enjoy the show. Just so you know, if you're listening, it's curtjaimungal.substack.com.