3 ms·

Not to say that I think that the world is a simulation or anything like that (I don't), but I think that computational complexity and related things probably do

by drdeca 9y ago

Not to say that I think that the world is a simulation or anything like that (I don't), but I think that computational complexity and related things probably do induce a natural notion of "naturality" on the different mappings. Even if there might not be a single most natural mapping, I think it makes sense to say that some mappings are more natural than others. I think there is a natural sense which is independent from human perception and intent, in which a computer running, say, a graph coloring algorithm, is doing that more than a waterfall is. Even if there is a bijection between a collection of initial states of the waterfall with the input of program, that fits together with one between the outputs and the results of the waterfall.

whatshisface 9y ago
Computational complexity is an insufficient motivator, because while in our current universe some problems are hard and others are easy, in the hypothetical universe there might be a law of physics that solves NP-hard problems. In fact, if the problem is right, you might even end up in a situation where they can't hook their NP-hard problem solvers together in a way that solves problems that we would consider polynomial.
- drdeca 9y ago
  > in the hypothetical universe there might be a law of physics that solves NP-hard problems I agree with this part. I wasn't thinking specifically about P vs NP though. (if I was, I think that would be a kind of weak argument because we don't have a proof that P isn't equal to NP ? At least not yet.) I was thinking more in terms of like, Solomonoff probability and Kolmorogov and things like that. And even if you suppose that the universe in question has a Turing oracle, I think you would just have to go up enough levels in that hierarchy in order solve that. Even without that though, looking at the space of permutations on N, I think it is likely that there is a natural way to talk about what things are true of "most" things in that space, and things like that, which could, I think, support at least a weak sense of degrees of naturality between mappings, even without appealing to computational complexity. Edit: I figured I should respond to this part also: > In fact, if the problem is right, you might even end up in a situation where they can't hook their NP-hard problem solvers together in a way that solves problems that we would consider polynomial. I think that whatever process is needed to get the output in a form that can be used as input for other things in general should be considered to be part of the computational process. Maybe that should even be implied by the meaning of "compute". Like, say that some computation takes a number as input in a binary representation, and outputs a number, but outputs it in ternary. If you are talking about how fast the process is on numbers, it should include the time needed to convert back to the binary representation. (Unless, of course, the computation that you are considering the process to be doing includes the "input is in binary, output is in ternary" part. If it is being considered "on numbers" though, I think it should include the conversion time to and from whatever representation of numbers is being considered to be canonical.)

by drdeca 9y ago

whatshisface 9y ago

Computational complexity is an insufficient motivator, because while in our current universe some problems are hard and others are easy, in the hypothetical universe there might be a law of physics that solves NP-hard problems. In fact, if the problem is right, you might even end up in a situation where they can't hook their NP-hard problem solvers together in a way that solves problems that we would consider polynomial.

drdeca 9y ago
> in the hypothetical universe there might be a law of physics that solves NP-hard problems I agree with this part. I wasn't thinking specifically about P vs NP though. (if I was, I think that would be a kind of weak argument because we don't have a proof that P isn't equal to NP ? At least not yet.) I was thinking more in terms of like, Solomonoff probability and Kolmorogov and things like that. And even if you suppose that the universe in question has a Turing oracle, I think you would just have to go up enough levels in that hierarchy in order solve that. Even without that though, looking at the space of permutations on N, I think it is likely that there is a natural way to talk about what things are true of "most" things in that space, and things like that, which could, I think, support at least a weak sense of degrees of naturality between mappings, even without appealing to computational complexity. Edit: I figured I should respond to this part also: > In fact, if the problem is right, you might even end up in a situation where they can't hook their NP-hard problem solvers together in a way that solves problems that we would consider polynomial. I think that whatever process is needed to get the output in a form that can be used as input for other things in general should be considered to be part of the computational process. Maybe that should even be implied by the meaning of "compute". Like, say that some computation takes a number as input in a binary representation, and outputs a number, but outputs it in ternary. If you are talking about how fast the process is on numbers, it should include the time needed to convert back to the binary representation. (Unless, of course, the computation that you are considering the process to be doing includes the "input is in binary, output is in ternary" part. If it is being considered "on numbers" though, I think it should include the conversion time to and from whatever representation of numbers is being considered to be canonical.)