Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: philosophy

Topic: physical implementation of abstract computations

Riley Shahar (Dec 14 2024 at 20:15):

Jencel Panic said:

It's pretty off topic from category theory, but you might be interested in the philosophical discussion about physical implementation of computations, which asks essentially "given some mathematical gadget which models a computation, say a DFA or Turing machine, when does a real-world physical system implement that computation?"

Haven't read about this, but I have thought about the question and the answer for me is pretty simple --- intend. A computer is a mechanism that was made in order to compute by people. Even if it doesn't compute correctly it is still a computer, just a defunct computer.

Interesting to hear your opinion, but we should probably open another topic :)

I think "what is a computer" is a different question (albeit an interesting one in its own right!) from the one I originally asked. Intent is not very compelling to me as an account of physical implementation of abstract computations. For instance:

• If I try to write code to test prime-checking, but due to a bug the code always returns true, is the computer actually realizing a prime-checking Turing machine?
• When I perform long division by hand---or, better, in my head---do I realize a dividing Turing machine?

I think the right account, whatever it is, should answer no to the first question and yes to the second. Your definition certainly answers yes to the first question; I think we could argue about what it answers for the second. So I think it doesn't really do what we want in paradigmatic examples.

Riley Shahar (Dec 14 2024 at 20:19):

Zooming out---one of the reasons philosophers are interested in this question is to try to use a theory of computation as the basis for a theory of the mind. This is a very classical idea in cognitive science; in particular it is one of the best-understood alternatives to behaviorism. But it requires that we distinguish between computational systems---those that compute, which if you believe all of this should include minds---and computers---which are often taken to be programmable in some way.

Madeleine Birchfield (Dec 14 2024 at 20:46):

Riley Shahar said:

I think the right account, whatever it is, should answer no to the first question and yes to the second.

The answer to the second question depends upon the shape of the universe. We already know from quantum mechanics and particle physics that ultimately matter and information is discrete. If the density parameter of the universe is greater than 1, then the shape of the universe is like $S^3$ and thus the universe is finite, meaning that no physical implementation of computation can realize a Turing machine. We can realize a Turing machine in a physical implementation if and only if the density parameter of the universe is less than or equal to 1 implying that the universe is infinite.

Riley Shahar (Dec 14 2024 at 20:54):

Madeleine Birchfield said:

Riley Shahar said:

I think the right account, whatever it is, should answer no to the first question and yes to the second.

The answer to the second question depends upon the shape of the universe. We already know from quantum mechanics that ultimately matter and information is discrete. If the density parameter of the universe is greater than 1, then the shape of the universe is like $S^3$ and thus the universe is finite, meaning that no physical implementation of computation can realize a Turing machine.

I agree with the substance of what you say, but I think it is a little reductive. Certainly either no or very few physical systems perfectly model Turing machines, in the sense of literally soundly and completely embedding the mathematical object inside of the physical world, for the reasons you say. But I still think there is something meaningful happening when I write a computer program that follows an abstract algorithm, even if that algorithm operates on an abstract machine with infinite memory and my computer has only finite memory. In paritcular, there is a meaningful sense in which my computer implements the Turing machine/DFA/whatever for some finite time. The interesting philosophical question is how to account for that kind of behavior---what is the relationship in cases like this between the mathematical model and the physical system?

Madeleine Birchfield (Dec 14 2024 at 20:58):

I think there should be some notion of "approximate Turing machine" with finite memory of size $n$, which behaves like a Turing machine except for some weird edge cases and which converges to an actual Turing machine in the limit of $n \to \infty$.

Riley Shahar (Dec 14 2024 at 20:59):

sure

Riley Shahar (Dec 14 2024 at 21:00):

Then you can ask what it means for a physical system with $k$ states to implement a "finite turing machine" with $n \leq k$ states. But I think the interesting question is going to be in what we mean when we say implement/realize/etc, not in the specific mathematical model of computation we choose to care about.

Riley Shahar (Dec 14 2024 at 21:05):

For instance, it's perfectly possible to write down a mathematically satisfactory definition of a finite physical system implementing a turing machine during some bounded period of time. Putnam did this in 1960; the definition is roughly that you should have a map from states of the turing machine to states of the physical system that respects state transitions during that bounded period. (You have to be a little careful to specify what you mean by a "time step" of the physical system which corresponds to one step of the machine, but this is all worked out by Putnam.) If the physical system is finite, you will never be able to do this for more than a bounded number of steps. But you can definitely write down the definition; it just happens to have philosophical properties that we don't like, basically because these maps are too plentiful to give a meaningful notion of computation. So the essence of the problem is philosophical, not mathematical.

Madeleine Birchfield (Dec 14 2024 at 21:19):

The other thing that I'm thinking about is the concept of an analog computer. Abstractly these assume an uncountable subspace of $\mathbb{R}^3$ so that they can compute solutions to differentiable equations, and thus are not implementable in a Turing machine.

In the real world, they run into the microscopic limits of quantum mechanics where theoretical predictions of how analog computers behave break down. Analog computers also rely on measurements which can be very uncertain in the real world.

Madeleine Birchfield (Dec 14 2024 at 21:25):

Where does quantum computing fit into the picture?

Riley Shahar (Dec 14 2024 at 21:44):

Great thoughts.

Riley Shahar (Dec 14 2024 at 21:45):

Madeleine Birchfield said:

Where does quantum computing fit into the picture?

I know there are some people who think quantum computing should make a big difference to this discussion, but I was never really convinced of why. (I guess I should be clear that I spent some serious time on this in undergrad, but I'm by no means an expert or even a trained philosopher.) I think most of the accounts in the literature work essentially the same way if you substitute a model of classical computation with a model of quantum computation. This is something we would probably have to treat on a case-by-case basis---i.e. if there's some account of implementation that we think might be affected by the shift from classical to quantum computation, we would have to look at that individually. I don't know that I can think of something general to say. (It would be cool if you did have something general to say, though!)

Riley Shahar (Dec 14 2024 at 21:48):

Madeleine Birchfield said:

The other thing that I'm thinking about is the concept of an analog computer. Abstractly these assume an uncountable subspace of $\mathbb{R}^3$ so that they can compute solutions to differentiable equations, and thus are not implementable in a Turing machine.

In the real world, they run into the microscopic limits of quantum mechanics where theoretical predictions of how analog computers behave break down. Analog computers also rely on measurements which can be very uncertain in the real world.

I haven't thought about this at all! Are there robust mathematical models of analog computation? In the literature people mostly work with combinatorial models of digital computation; it would be interesting to take some of the accounts that have been robustly defined in that setting and try to translate them to some good model of analog computation.

Madeleine Birchfield (Dec 14 2024 at 22:24):

Riley Shahar said:

I haven't thought about this at all! Are there robust mathematical models of analog computation? In the literature people mostly work with combinatorial models of digital computation; it would be interesting to take some of the accounts that have been robustly defined in that setting and try to translate them to some good model of analog computation.

I have no idea myself of any mathematical models of analog computation. But this is kind of a big problem for the entire field right now, that they mostly work with combinatorial models of digital computation.

If we want to postulate a theory of computation as a basis for a theory of mind, as you indicated in your original post, well the human brain would be an analog computer in the theory, and the dearth of mathematical models of analog computing means that we don't really understand how computation occurs in the brain.

More generally, biological computation is considered to be analog computation.

Riley Shahar (Dec 14 2024 at 22:40):

The goal is not really to understand how computation occurs in the brain---I'd say that is a neurobiological question by now. (And as the page you link to suggests, it's one that's actively being investigated by biologists.) The goal of this vein of cognitive philosophy to try to figure out what it is for something to have a mind (or maybe to be conscious, etc). The classical answer is behavioral---to have a mind is to exhibit a certain set of behaviors---but there are a number of problems with this, e.g. p-zombies, etc. So one alternative is to say that a mind is a physical system which implements an abstract computation with certain properties. This is not a behavioral theory, because there are distinct computations with the same external behavior. It also is related to, but distinct from, the actual computational structure of the brain. Under any of the standard accounts of computation in the literature, I strongly suspect that physical analog computers will indeed implement certain abstract combinatorial computations. So even if the brain is an analog computer in some sense (I'm not really sure what that would mean?), it can still be described by the existing theories.

The direction I haven't thought about is whether we can shift these theories to be based on an abstract analog model of computation. That is not the same as whether the theories can account for physical analog computers.

Riley Shahar (Dec 14 2024 at 22:44):

Riley Shahar said:

So one alternative is to say that a mind is a physical system which implements an abstract computation with certain properties.

To pin down such a theory, we need to know:

• What is it for a physical system to implement an abstract computation?
• What are the properties which distinguish those abstract computations that are cognitive, in that their physical implementors have minds?

If you give some reasonable answer to both these questions, you have specified a computational theory of mind. So there is a lot of literature on both of them. We've been talking about the first, which I know a lot more about.

Riley Shahar (Dec 14 2024 at 22:45):

(To be honest, I'm not totally convinced of this approach to the philosophy of mind, but it's far from the worst approach to this issue, and anyway the first question is interesting in its own right.)

John Baez (Dec 14 2024 at 22:47):

I think it's a bit distracting to think of what the human brain and body do as "computation", except in cases like when I'm mentally multiplying 4 and 23, which actually is one of the things the brain does worst. Of course, we are free to treat any physical process as a "computation" if we like. But this way of thinking seems to be the most useful for processes that resemble what human-made computers do, where we've developed a large apparatus of useful ideas: the whole elaborate language of computer science. Whatever the brain and body are doing, it doesn't look much like what any human-made computer is doing. There's no "program", there's no clear distinction between "data" and random wiggling of biomolecules, there's no clear "input" and "output", etc.

Madeleine Birchfield (Dec 14 2024 at 22:49):

John Baez said:

I think it's a bit distracting to think of what the human brain and body do as "computation", except in cases like when I'm mentally multiplying 4 and 23, which actually is one of the things the brain does worst.

Well, in that case, it might simply be that this

Riley Shahar said:

Zooming out---one of the reasons philosophers are interested in this question is to try to use a theory of computation as the basis for a theory of the mind.

might not simply be possible.

Riley Shahar (Dec 14 2024 at 22:49):

John Baez said:

I think it's a bit distracting to think of what the human brain and body do as "computation", except in cases like when I'm mentally multiplying 4 and 23, which actually is one of the things the brain does worst. Of course, we are free to treat any physical process as a "computation" if we like. But this way of thinking seems to be the most useful for processes that resemble what human-made computers do, where we've developed a large apparatus of useful ideas: the whole elaborate language of computer science. Whatever the brain and body are doing, it doesn't look much like what any human-made computer is doing. There's no "program", there's no clear distinction between "data" and random wiggling of biomolecules, there's no clear "input" and "output", etc.

Yeah---this is exactly why, as I said. I'm not convinced of this approach. I only mentioned it in the first place because I wanted to give some motivation for considering "computing systems" as distinct from "programmable computers."

Madeleine Birchfield (Dec 14 2024 at 22:50):

I should also point to the existence of neuromorphic computing as a possible counterargument against John Baez's paragraph. I'm not sure if neuromorphic computing would even count as computing according to his standards.

Riley Shahar (Dec 14 2024 at 22:56):

John Baez said:

There's no "program", there's no clear distinction between "data" and random wiggling of biomolecules, there's no clear "input" and "output", etc.

Actually because there's no clear distinction between program and data in many physical systems, it's more common to think about physical systems implementing automata rather than genuine turing machines. Classically, they work with "input-output automata." which at each step take some input from a fixed alphabet, then transition on their state graph, then give some output from a fixed alphabet. Then maybe we can find a mapping from the states of a (non-closed) physical system to the states of the automaton that respects state transitions and input-output dependencies, in which case maybe we could say that (by quotienting together physical states which correspond to the same abstract state) is somehow "implementing" that automaton. (I think it's reasonable to avoid the word "computation" here.) But as you say, you're very likely to be able to do this for any small automaton because there are so many particles wiggling basically at random in physical systems. So people usually ask that the mapping respects more then just transitions.

Riley Shahar (Dec 14 2024 at 22:59):

Madeleine Birchfield said:

I should also point to the existence of neuromorphic computing as a possible counterargument against John Baez's paragraph. I'm not sure if neuromorphic computing would even count as computing according to his standards.

This stuff sounds cool! But unlike human brains, there is a sense in which these devices are programmed, because I assume people design them to do something in particular. So if our definition of computer includes programmability, probably we can get away with saying these are computers while the brain is not.

John Baez (Dec 14 2024 at 23:12):

Neuromorphic computing is people using digital computers, which we understand pretty well, to simulate highly simplified models of what the brain does. That's great! I love it.

But it's quite different than what the brain actually does. It might someday become more and more like what the brain actually does... but so far people are engaged in a large project, not yet complete, to accurately simulate one cell of a bacterium far simpler that a human cell (Mycoplasmum genitalium). The brain has about 170 billion cells, and we cannot actually simulate a brain separate from the rest of the body and get a good understanding of what humans do.

Madeleine Birchfield (Dec 14 2024 at 23:12):

Riley Shahar said:

Actually because there's no clear distinction between program and data in many physical systems, it's more common to think about physical systems implementing automata rather than genuine turing machines.

Automata can implement Turing machines though, such as rule 110.

Madeleine Birchfield (Dec 14 2024 at 23:16):

John Baez said:

Neuromorphic computing is people using digital computers, which we understand pretty well, to simulate highly simplified models of what the brain does.

It really isn't. The specialised hardware designed for and used in neuromorphic computing aren't the same as the hardware that is used as digital computers, and they tend to rely on analog physical phenomena rather than digital logic circuits.

Madeleine Birchfield (Dec 14 2024 at 23:23):

See i.e. Neurogrid, which is an analog neuromorphic computer used to simulate spiking neural networks.

Madeleine Birchfield (Dec 14 2024 at 23:25):

What you mean by "neuromorphic computing" is creating models of the brain / neural networks as software on a digital computer, which is not the same thing. That tends to be called "computational neuroscience" in the actual literature, with the term "neuromorphic computing" reserved for the specialised hardware.

John Baez (Dec 15 2024 at 00:53):

Okay, analog computing begins to approach the 'messiness' of real-world biology, where it's often hard or impossible to do what we do routinely in digital computation: draw a sharp line between the 'relevant' degrees of freedom and the 'irrelevant' ones, in such a way that the irrelevant ones don't affect future values of relevant ones. E.g. we treat memory cells as being 'on' if some voltage is higher than a certain amount, and 'off' if it's lower than some other amount - and we carefully set things up so that the precise value of the voltage is irrelevant: only whether it's 'on' or 'off' is relevant.

This is what makes a digital computer more easy to understand than a bacterium. But this is also connected to why, if you throw a digital computer into the jungle, it's less likely to survive. It's even true for an analogue computer. Many details of the atoms of its metal parts don't matter much when these parts are working properly - we can consider them 'irrelevant' to the computing it does - but the rain will rust the metal and the computer doesn't have a self-repair process that can fight against this rust.

John Baez (Dec 15 2024 at 00:55):

Riley Shahar said:

Actually because there's no clear distinction between program and data in many physical systems, it's more common to think about physical systems implementing automata rather than genuine Turing machines.

Before I was calling all relevant degrees of freedom 'data', which was confusing. So let me stop doing that.

I'm trying to say that in digital computing, but not biology, there's a quite sharp divide between the relevant and irrelevant degrees of freedom. This is different from the distinction between programs and data; in a digital computer both programs and data involve only relevant degrees of freedom.

Alex Kreitzberg (Dec 15 2024 at 05:10):

You can give a really concrete example of one of the purported problems philosophers are stressed about here. I think that belongs in this discussion somewhere. @Riley Shahar , if you can, please verify that my example is honest to the problem, I'm not a philosopher.

Gualtiero Piccinini summarized Putnam's "simple mapping account" into two rules (Here I'm using Putnam's terminology "physical description" instead of Piccinini's "microphysical description")

Let $S$ be a physical system, and $C$ a computational system. We have a simple mapping from S to C when

• There is a mapping from a subset of (or equivalence classes of) the states ascribed to S by a physical description to the states defined by computational description C.

• The state transitions between the physical states mirror the state transitions between the computational states.

To me, this definition seems like our mapping is required to be a functor.

A common criticism of this definition, is it's too easy to come up with simple mappings. Here's my example of one "too simple" mapping.

Here's a table for a certain simple computation I just threw together:

I'm imagining a machine in either state $A$ or $B$ deciding how to rewrite a single square depending on what it reads. For example, a machine in state $A$ reading $t$ will move to state $B$ and rewrite $t$ to $f$.

So $(A, t) \rightarrow (B, f) \rightarrow (A, f) \rightarrow (A, f) \rightarrow \ldots$
In general any computation will provide at least one sequence $s_1, s_2, \ldots, s_n, \ldots$.

Now take a thermometer out of the fridge, and leave it in the sun. You'll get an increasing function, describing temperature over time.

To make our simple mapping $f : \frac{S}{\sim} \rightarrow C$, Map the temperatures the thermometer takes in the first second to $s_1$, the temperatures in the second second to $s_2$, and the temperatures in the third second to $s_3$, and so on.

Now $f(t_1) = s_1, f(t_2) = s_2, f(t_3) = s_3, \ldots$. This satisfies both of our requirements.

If you think there's no problem with the above, then you're a "pancomputationalist"

The strongest version of pancomputationalism is that every physical system performs every computation—or at least, every sufficiently complex system implements a very large number of non-equivalent computations (Putnam 1988, Searle 1992). This may be called unlimited pancomputationalism.

I hope I represented the problem fairly. The question at issue here isn't really about computation. I understand it as closer to something like "how is it possible to not be confused by this huge bunch of silly maps? There is some set of distinguished mappings right?" Or maybe you don't like mappings and think they're confusing the issue somehow, etc.

When I first thought about this, I worried understanding these issues too much would be sort of like making myself go blind by learning how to control each of my eyes independently. So I decided to put this stuff down until I was more comfortable with categorical math.

But, being aware of the above, does give me a modicum of anxiety when I'm trying to decide how some physical thingy corresponds to some mathematical thingy.

Jencel Panic (Dec 15 2024 at 08:40):

Riley Shahar said:

I think "what is a computer" is a different question (albeit an interesting one in its own right!) from the one I originally asked. Intent is not very compelling to me as an account of physical implementation of abstract computations. For instance:

• If I try to write code to test prime-checking, but due to a bug the code always returns true, is the computer actually realizing a prime-checking Turing machine?
• When I perform long division by hand---or, better, in my head---do I realize a dividing Turing machine?

I think the right account, whatever it is, should answer no to the first question and yes to the second. Your definition certainly answers yes to the first question; I think we could argue about what it answers for the second. So I think it doesn't really do what we want in paradigmatic examples.

Oh, I didn't expect so much interest in this topic :) A couple of points from your response:

1. The part about the wrong computations was figurative, if you want to filter out all partly-working computer, we can easily augment the definition to do so.
2. Take the word "computer" in it's broadest sense --- a person doing a computation is a computer. Actually, as you probably know, that the the word "computer" originally meant exactly this!

Jencel Panic (Dec 15 2024 at 08:47):

I do realize that my definition is not what these people are on a lookout of, because it relies on the concept of an agent, the thinking being. But almost all philosophy does require this concept. That is pretty much what philosophy is.

Peva Blanchard (Dec 15 2024 at 10:57):

Jencel Panic said:

2. Take the word "computer" in it's broadest sense --- a person doing a computation is a computer. Actually, as you probably know, that the the word "computer" originally meant exactly this!

If I recall correctly, this is the Church-Turing thesis that states that the Turing machine model is the definition of a "computer in its broadest sense". More precisely, in its original formulation, it states the equivalence between the informal notion of "effectively computable function" and the formal model of a Turing machine.

There have been variants of the thesis that extend its original scope. In particular, there are "physical Church-Turing thesis" variants (sorry I don't have the reference at hand): they more or less state the equivalence between the informal notion of "physically feasible process"and the formal Turing machine.

Quite interestingly, some people have tried to imagine physical universes where the Halting problem could be solved. As far as I remember, every attempt involved "crazy" assumptions, e.g., travel back in time. Of course, the fact that no one managed to imagine a physical mechanism, in our current understanding of our universe, that can solve the Halting problem, doesn't prove the physical Church-Turing thesis.

Scott Aaronson went further down that road by asking Can NP-complete problems be solved efficiently in the physical universe?.

Riley Shahar (Dec 15 2024 at 18:26):

John Baez said:

Riley Shahar said:

Actually because there's no clear distinction between program and data in many physical systems, it's more common to think about physical systems implementing automata rather than genuine Turing machines.

Before I was calling all relevant degrees of freedom 'data', which was confusing. So let me stop doing that.

I'm trying to say that in digital computing, but not biology, there's a quite sharp divide between the relevant and irrelevant degrees of freedom. This is different from the distinction between programs and data; in a digital computer both programs and data involve only relevant degrees of freedom.

Ah. Yes, I agree. This is one of the major issues in the philosophy literature to giving a satisfactory account of physical computation.

John Baez (Dec 16 2024 at 02:37):

Madeleine Birchfield said:

We already know from quantum mechanics and particle physics that ultimately matter and information is discrete. If the density parameter of the universe is greater than 1, then the shape of the universe is like $S^3$ and thus the universe is finite, meaning that no physical implementation of computation can realize a Turing machine. We can realize a Turing machine in a physical implementation if and only if the density parameter of the universe is less than or equal to 1 implying that the universe is infinite.

There are many things to discuss here, but according to what we seem to know about cosmology today, no civilization is capable of carrying out arbitrarily large computations even though the universe seems unbounded in spatial extent, because it's expanding exponentially and the number of galaxies anyone can reach will keep decreasing as they slip out of the grasp of anyone who can't go faster than light. All this is somewhat counterintuitive - you need to think about general relativity fairly hard to see why it's true - but Toby Ord has a nice paper about it and I summarized it briefly here:

• The expansion of the Universe.

(His paper is open-access, so read that if you care about the details.)

If we wait long enough we'd be able to reach arbitrarily large regions of nearly-empty intergalactic space, but I don't believe it's possible to do computations in space where the density of atoms is very low to begin with and decreasing exponentially.

I think the main uncertainty here is that we don't know the last word on physics: "we", meaning life in the Universe, might discover brand new tricks based on physical laws we don't know yet.

John Baez (Dec 16 2024 at 03:02):

A more practical point is that nobody knows how to build a computer as powerful as a Turing machine, because it would require access to unbounded amounts of memory, and that's okay, because Turing computability is an idealization, and an upper bound on what we can do - and we work with it as such.

Martti Karvonen (Dec 16 2024 at 08:40):

Riley Shahar said:

For instance, it's perfectly possible to write down a mathematically satisfactory definition of a finite physical system implementing a turing machine during some bounded period of time. Putnam did this in 1960; the definition is roughly that you should have a map from states of the turing machine to states of the physical system that respects state transitions during that bounded period. (You have to be a little careful to specify what you mean by a "time step" of the physical system which corresponds to one step of the machine, but this is all worked out by Putnam.) If the physical system is finite, you will never be able to do this for more than a bounded number of steps. But you can definitely write down the definition; it just happens to have philosophical properties that we don't like, basically because these maps are too plentiful to give a meaningful notion of computation. So the essence of the problem is philosophical, not mathematical.

A bit late to the discussion, but I quite like Scott Aaronson's point on this (section 6 here). Roughly speaking, in his opinion we should take computational complexity of the mapping into account - if the mapping is "doing all the work", then arguably the system in question is not doing the computation mapped to it.

Notification Bot (Dec 16 2024 at 10:48):

A message was moved from this topic to #theory: philosophy > Church-Turing thesis by Peva Blanchard.

Riley Shahar (Dec 16 2024 at 18:19):

Martti Karvonen said:

A bit late to the discussion, but I quite like Scott Aaronson's point on this (section 6 here). Roughly speaking, in his opinion we should take computational complexity of the mapping into account - if the mapping is "doing all the work", then arguably the system in question is not doing the computation mapped to it.

Cool! Thank you for sharing that article, which I haven't seen before and looks really interesting. I read section 6 (will definitely read the rest later). I guess I should say that these issues have also been extensively considered by philosophers and cognitive scientists, e.g. here, where the authors argue that only tractable computations can possibly form a basis for a theory of mind. The bibliography there is fairly extensive.

That said, I'm not convinced that complexity bounds alone can get us out of computational trivialism. In particular, the waterfall argument as Aarsonson articulates it is merely about input-output dependencies, but there are other versions (e.g. the "clock-and-dial" construction of Chalmers) which show that any DFA embeds into any sufficiently complex system with enough states, which is a much stronger result. It's unclear to me what complexity theory has to say about this absent some way to distinguish between "relevant" and "irrelevant" states (for instance via an encoding of states into binary which has some particular information-theoretic properties, so that distinguishing between irrelevant states is computationally intractable), as we discussed above. So I think we still need some kind of extra structure, causal or semantic or etc.

But maybe complexity theory does say something about this kind of mapping that I don't see right now? I'm sure Aaronson knows this stuff a million times better than I do, lol.