As someone who can follow the 5 and 10 problem, but who doesn’t really internalize why it matters (no matter how many times I look at similar explainers, I always just come away with “don’t do that! recursion without exit conditions is taught as a bad thing to elementary school coders. OF COURSE a thing can’t contain a perfect model of itself plus any other stuff.”)
I’m sorry to report that this version uses a lot more words than most, but the object values (route selection) are so disconnected from the main point that it doesn’t shed any light on the problem.
How oh how did things go so tragically wrong for our autonomous car?
There’s a one-line answer: the builders weren’t trying to make a car pick a route, they were trying to … I don’t actually know what.
the builders weren’t trying to make a car pick a route, they were trying to … I don’t actually know what.
Well there is a perspective from which the algorithm used here can seem very compelling. After all, what could make more sense than considering each possible action, searching for a proof that connects each action to its consequences, and then picking the action with the most desirable consequences? This is what the proof search algorithm does. It is deeply surprising that it fails so completely. I should have made that clearer in the post.
recursion without exit conditions is taught as a bad thing to elementary school coders
The algorithm here is not actually recursive. The proof search is just a straightforward loop through all possible proofs up to some length limit. Checking the validity of a proof means checking whether each step follows deductively from the previous steps. It does not involve any recursion, not even one level of recursion, and certainly not recursion without exit conditions.
OF COURSE a thing can’t contain a perfect model of itself plus any other stuff
In what way is it not possible for a thing to contain a perfect model of itself? A computer can certainly contain a circuit diagram of itself on a file on its hard drive. A program can certainly contain a copy of its own source code inside a string. Humans are capable of comprehending their own anatomy and neurology, apparently without any fixed limit. In what way can a thing not contain a model of itself?
I think your definition of perfect model is a bit off—a circuit diagram of a computer is definitely not a perfect model of the computer! The computer itself has much more state and complexity, such as temperature of the various components, which are relevant to the computer but not the model.
Containing a copy of your source code is a weird definition of a model. All programs contain their source code, does a program that prints it source code have more of a model of itself than other programs, which are just made of their source code? Human brains are not capable of holding a perfect model of a human brain, plus more, because the best-case encoding requires using one atom of the human brain to model an atom in the human brain, leaving you at 100% capacity.
The key word is “perfect”—to fit a model of a thing inside that thing, the model must contain less information than the thing does.
I think your definition of perfect model is a bit off—a circuit diagram of a computer is definitely not a perfect model of the computer! The computer itself has much more state and complexity, such as temperature of the various components, which are relevant to the computer but not the model.
But there is no fundamental law of physics that says that the computer cannot maintain estimates of the temperature of each of its components.
Now it is true that a computer cannot store the exact physical state of every atom that constitutes it, since storing that much information would indeed require the full physical expressivity of every atom that constitutes it, and there would indeed be no room left over to do anything else.
But digital computers are designed precisely so that their behavior can be predicted without needing to track the exact physical state of every atom that constitutes them. Humans are certainly able to reason about computers in quite a bit of detail without tracking the exact physical state of every atom that constitutes them. And there is no reason that a digital computer couldn’t store and use a self-model with at least this level of predictive power.
Containing a copy of your source code is a weird definition of a model. All programs contain their source code, does a program that prints it source code have more of a model of itself than other programs, which are just made of their source code?
Well sure, containing a copy of your own source code on its own is not really a “self-model”, but it does show that there is nothing fundamentally blocking you from analyzing your own source code, including proving things about your own behavior. There is nothing fundamentally paradoxical or recursive about this. The claim was made that things cannot contain perfect models of themselves, but in fact things can contain models of themselves that are sufficiently to reason about.
The key word is “perfect”—to fit a model of a thing inside that thing, the model must contain less information than the thing does.
Well yes, but the autonomous car in the parable didn’t go wrong by having an insufficiently perfect self-model. It had a self-model quite sufficient to make all the predictions it needed to make. If the self-model had been more detailed, the car still would have gone wrong. Even if it had a truly perfect self-model, even though such a thing is not permitted under our laws of physics, it still would have gone wrong. So the problem isn’t about the inability for things to contain models of themselves. It’s about how those self-models are used.
considering each possible action, searching for a proof that connects each action to its consequences, and then picking the action with the most desirable consequences?
I’m clearly seriously misunderstanding something about proofs. My understanding of Gödel’s theorem, and general complexity theory, lead me to find that mechanism VERY un-compelling. There may be aspects you want to prove (or disprove), but there are going to be important decisions that are unprovable, and many (most, I think) theoretically-provable outcomes will be computationally infeasible. And that’s my belief before even considering the counterfactual problem (false implies everything).
I’ll need to think more about why this feels like recursion—my intuition is handwavey at this point, related to the agent deciding by evaluating the agent’s choice, rather than deciding by removing the agent in each branch.
A computer can certainly contain a circuit diagram of itself on a file on its hard drive.
Sure, but those aren’t computations. they’re compressed representations, which requires a lot more resources to simulate. And if that circuit/source includes the execution of the resulting structures (aka emulation), we’re back to recursion, in which each iteration consumes additional resources.
Sure, but those aren’t computations. they’re compressed representations, which requires a lot more resources to simulate. And if that circuit/source includes the execution of the resulting structures (aka emulation), we’re back to recursion, in which each iteration consumes additional resources.
Can you give me an example of something that cannot be done by a computer that is attempting to reason about its own circuitry?
Do you mean that since the computer is using some of its processing power to analyze its own circuitry, it cannot therefore dedicate 100% of its processing power to any other process running on the system? Or do you mean that it cannot use all of its processing power to analyze its own circuitry, even if there are no other processes running on the system?
The former I agree with, but that is true of any process whatsoever—e.g. if the computer is running a game of solitaire then that process will use up some non-zero amount of processing power, which the computer therefore cannot devote to any other process.
The latter I disagree with. Let’s say that the computer is running an analysis of its circuitry that can be expressed as a SAT problem (as many real-world hardware verification problems can be). So the computer loads the representation of its circuitry, constructs a SAT problem, then begins searching over the possible variable assignments looking for a solution. Why couldn’t the computer dedicate its full capacity at full speed to this search?
for a given set of resources (cpu-time or instruction count, reads/writes/total storage, etc.), there are computations that can be done directly, which cannot be done in an emulator which takes some of those resources.
There is some amount of underlying useful work that’s being done (calculating expected value of hypothetical actions) which is feasible to directly calculate, and infeasible to calculate the calculation.
When the useful work IS the emulation, then of course it’s using it’s full power. But it can’t emulate and verify the emulation/verification (without additional resources).
Why are you talking about emulation? There are lots of ways to analyze a circuit diagram other than emulation. The autonomous car in the story does not use emulation.
That’s an excellent question—I don’t know if the connection between formal proof and emulation/reflection exists anywhere outside of my mind. I believe my arguments hold for the impossibility of proving something without additional resources over just calculating it (possibly using a method that has proofs about it’s correctness, which happened outside the computation itself).
As someone who can follow the 5 and 10 problem, but who doesn’t really internalize why it matters (no matter how many times I look at similar explainers, I always just come away with “don’t do that! recursion without exit conditions is taught as a bad thing to elementary school coders. OF COURSE a thing can’t contain a perfect model of itself plus any other stuff.”)
I’m sorry to report that this version uses a lot more words than most, but the object values (route selection) are so disconnected from the main point that it doesn’t shed any light on the problem.
There’s a one-line answer: the builders weren’t trying to make a car pick a route, they were trying to … I don’t actually know what.
Well there is a perspective from which the algorithm used here can seem very compelling. After all, what could make more sense than considering each possible action, searching for a proof that connects each action to its consequences, and then picking the action with the most desirable consequences? This is what the proof search algorithm does. It is deeply surprising that it fails so completely. I should have made that clearer in the post.
The algorithm here is not actually recursive. The proof search is just a straightforward loop through all possible proofs up to some length limit. Checking the validity of a proof means checking whether each step follows deductively from the previous steps. It does not involve any recursion, not even one level of recursion, and certainly not recursion without exit conditions.
In what way is it not possible for a thing to contain a perfect model of itself? A computer can certainly contain a circuit diagram of itself on a file on its hard drive. A program can certainly contain a copy of its own source code inside a string. Humans are capable of comprehending their own anatomy and neurology, apparently without any fixed limit. In what way can a thing not contain a model of itself?
I think your definition of perfect model is a bit off—a circuit diagram of a computer is definitely not a perfect model of the computer! The computer itself has much more state and complexity, such as temperature of the various components, which are relevant to the computer but not the model.
Containing a copy of your source code is a weird definition of a model. All programs contain their source code, does a program that prints it source code have more of a model of itself than other programs, which are just made of their source code? Human brains are not capable of holding a perfect model of a human brain, plus more, because the best-case encoding requires using one atom of the human brain to model an atom in the human brain, leaving you at 100% capacity.
The key word is “perfect”—to fit a model of a thing inside that thing, the model must contain less information than the thing does.
But there is no fundamental law of physics that says that the computer cannot maintain estimates of the temperature of each of its components.
Now it is true that a computer cannot store the exact physical state of every atom that constitutes it, since storing that much information would indeed require the full physical expressivity of every atom that constitutes it, and there would indeed be no room left over to do anything else.
But digital computers are designed precisely so that their behavior can be predicted without needing to track the exact physical state of every atom that constitutes them. Humans are certainly able to reason about computers in quite a bit of detail without tracking the exact physical state of every atom that constitutes them. And there is no reason that a digital computer couldn’t store and use a self-model with at least this level of predictive power.
Well sure, containing a copy of your own source code on its own is not really a “self-model”, but it does show that there is nothing fundamentally blocking you from analyzing your own source code, including proving things about your own behavior. There is nothing fundamentally paradoxical or recursive about this. The claim was made that things cannot contain perfect models of themselves, but in fact things can contain models of themselves that are sufficiently to reason about.
Well yes, but the autonomous car in the parable didn’t go wrong by having an insufficiently perfect self-model. It had a self-model quite sufficient to make all the predictions it needed to make. If the self-model had been more detailed, the car still would have gone wrong. Even if it had a truly perfect self-model, even though such a thing is not permitted under our laws of physics, it still would have gone wrong. So the problem isn’t about the inability for things to contain models of themselves. It’s about how those self-models are used.
I’m clearly seriously misunderstanding something about proofs. My understanding of Gödel’s theorem, and general complexity theory, lead me to find that mechanism VERY un-compelling. There may be aspects you want to prove (or disprove), but there are going to be important decisions that are unprovable, and many (most, I think) theoretically-provable outcomes will be computationally infeasible. And that’s my belief before even considering the counterfactual problem (false implies everything).
I’ll need to think more about why this feels like recursion—my intuition is handwavey at this point, related to the agent deciding by evaluating the agent’s choice, rather than deciding by removing the agent in each branch.
Sure, but those aren’t computations. they’re compressed representations, which requires a lot more resources to simulate. And if that circuit/source includes the execution of the resulting structures (aka emulation), we’re back to recursion, in which each iteration consumes additional resources.
Can you give me an example of something that cannot be done by a computer that is attempting to reason about its own circuitry?
Sure. It can’t use it’s full capacity at full speed.
Do you mean that since the computer is using some of its processing power to analyze its own circuitry, it cannot therefore dedicate 100% of its processing power to any other process running on the system? Or do you mean that it cannot use all of its processing power to analyze its own circuitry, even if there are no other processes running on the system?
The former I agree with, but that is true of any process whatsoever—e.g. if the computer is running a game of solitaire then that process will use up some non-zero amount of processing power, which the computer therefore cannot devote to any other process.
The latter I disagree with. Let’s say that the computer is running an analysis of its circuitry that can be expressed as a SAT problem (as many real-world hardware verification problems can be). So the computer loads the representation of its circuitry, constructs a SAT problem, then begins searching over the possible variable assignments looking for a solution. Why couldn’t the computer dedicate its full capacity at full speed to this search?
for a given set of resources (cpu-time or instruction count, reads/writes/total storage, etc.), there are computations that can be done directly, which cannot be done in an emulator which takes some of those resources.
There is some amount of underlying useful work that’s being done (calculating expected value of hypothetical actions) which is feasible to directly calculate, and infeasible to calculate the calculation.
When the useful work IS the emulation, then of course it’s using it’s full power. But it can’t emulate and verify the emulation/verification (without additional resources).
Why are you talking about emulation? There are lots of ways to analyze a circuit diagram other than emulation. The autonomous car in the story does not use emulation.
That’s an excellent question—I don’t know if the connection between formal proof and emulation/reflection exists anywhere outside of my mind. I believe my arguments hold for the impossibility of proving something without additional resources over just calculating it (possibly using a method that has proofs about it’s correctness, which happened outside the computation itself).