Basically I think you’re confused. You correctly begin to identify the core of the problem and then don’t engage with it here:
It seems like what counts as a perfect simulation hides most of the complexity of this problem. For now, I’m going to hand wave a bit and say a perfect simulation is anything that can asses the truth value of a arbitrary proposition about the universe.
Interpreting this definition sufficiently strongly, the following straightforward diagonalization argument can be applied: suppose you had such a simulation, and that it had some sort of output channel that it used to display answers to questions about the universe. Ask it “is the answer to this question that’s about to be displayed in the output channel no?”
In the positive direction, there is the following lovely theorem: without loss of generality, you can always assume that a program has access to a copy of its own source code. Given this fact, one might try to apply the above diagonalization argument, as follows: a program attempts to run itself, outputting true if it outputs false, and outputting false if it outputs true. What happens?
Straightforward: the program doesn’t halt, outputting nothing; you can think of this as being the result of the program repeatedly calling itself over and over again. A slight modification of this argument produces the usual proof of the undecidability of the halting problem.
Basically I think you’re confused. You correctly begin to identify the core of the problem and then don’t engage with it here
Agreed, good catch.
I think that when I proposed that definition, I quickly thought “Well nothing like that could exist” then swapped out the definition with something very vague like, “A perfectly accurate simulation would be a thing that feels reasonable to call a perfect simulation, yet not as powerful as what I just described”, and then carried on reasoning from there.
Giving it more thought, I find the original definition of perfect simulation to be a good fit, and the original question is now resolved.
Though I no longer see the sub-string problem I proposed as relating to the original problem, I’m curious about what you think would be a meaningful definition of a “perfect encoding”.
I’m curious about what you think would be a meaningful definition of a “perfect encoding”.
Part of the point of the excerpt you quoted from Aaronson is that in any notion of an encoding, some of the computational work is being done by the decoding procedure, whatever that is. So e.g. you can specify a programming language, and build a compiler that will compile and execute programs in that programming language, and then talk about a program perfectly encoding something if it outputs that thing when run. Some of the computational work is being done by the program but some of it’s being done by the compiler.
Basically I think you’re confused. You correctly begin to identify the core of the problem and then don’t engage with it here:
Interpreting this definition sufficiently strongly, the following straightforward diagonalization argument can be applied: suppose you had such a simulation, and that it had some sort of output channel that it used to display answers to questions about the universe. Ask it “is the answer to this question that’s about to be displayed in the output channel no?”
In the positive direction, there is the following lovely theorem: without loss of generality, you can always assume that a program has access to a copy of its own source code. Given this fact, one might try to apply the above diagonalization argument, as follows: a program attempts to run itself, outputting true if it outputs false, and outputting false if it outputs true. What happens?
Straightforward: the program doesn’t halt, outputting nothing; you can think of this as being the result of the program repeatedly calling itself over and over again. A slight modification of this argument produces the usual proof of the undecidability of the halting problem.
Thanks for the feedback!
Agreed, good catch.
I think that when I proposed that definition, I quickly thought “Well nothing like that could exist” then swapped out the definition with something very vague like, “A perfectly accurate simulation would be a thing that feels reasonable to call a perfect simulation, yet not as powerful as what I just described”, and then carried on reasoning from there.
Giving it more thought, I find the original definition of perfect simulation to be a good fit, and the original question is now resolved.
Though I no longer see the sub-string problem I proposed as relating to the original problem, I’m curious about what you think would be a meaningful definition of a “perfect encoding”.
Part of the point of the excerpt you quoted from Aaronson is that in any notion of an encoding, some of the computational work is being done by the decoding procedure, whatever that is. So e.g. you can specify a programming language, and build a compiler that will compile and execute programs in that programming language, and then talk about a program perfectly encoding something if it outputs that thing when run. Some of the computational work is being done by the program but some of it’s being done by the compiler.