If I know an algorithm that outputs 1 or 0 depending on whether the input was prime or not, I can use a different prime checking algorithm without running the whole thing. So, for example, if the algorithm is naive trial division, I can predict its result very quickly using something like Agrawal’s algorithm or some variant of Miller-Rabin. This example is in some ways a toy example, but it isn’t obvious that one wouldn’t have similar examples for more complicated phenomena.
I’m not sure yet about wedrifid’s general point, but I have a few philosophical problems with this particular example.
If Trial Division and Miller-Rabin are functionally equivalent (compute the same results), then they simulate each other—correct? So this is not a counterexample.
And on another whole philosophical level, how do you know your algorithm actually computes whether the input was prime or not? (or how was that originally discovered? and did that discovery require simulation?)
Ultimately if the cortex uses approximate forward simulation, then we can’t do anything without some form of simulation.
If Trial Division and Miller-Rabin are functionally equivalent (compute the same results), then they simulate each other—correct? So this is not a counterexample.
This may come down to what you mean by simulate. Certainly a computer scientist would be unlikely to describe that as a simulation. And if you are asserting that anything with the same output as something else can be considered to be simulating it then your earlier claim becomes tautological. The then relevant issue becomes that this is an example where we can “simulate” something while using much less computation than running something is in complete detail (indeed, there’s very little resemblance in the internal workings).
And on another whole philosophical level, how do you know your algorithm actually computes whether the input was prime or not? (or how was that originally discovered? and did that discovery require simulation?)
I can prove things without simulating. One can look at code and determine what it does without simulating. The entire point of proving algorithms correct is that that’s done by mathematical proof, not by empirical testing for small values.
If I know an algorithm that outputs 1 or 0 depending on whether the input was prime or not, I can use a different prime checking algorithm without running the whole thing. So, for example, if the algorithm is naive trial division, I can predict its result very quickly using something like Agrawal’s algorithm or some variant of Miller-Rabin. This example is in some ways a toy example, but it isn’t obvious that one wouldn’t have similar examples for more complicated phenomena.
And any example is sufficient to reject a general absolute claim.
I’m not sure yet about wedrifid’s general point, but I have a few philosophical problems with this particular example.
If Trial Division and Miller-Rabin are functionally equivalent (compute the same results), then they simulate each other—correct? So this is not a counterexample.
And on another whole philosophical level, how do you know your algorithm actually computes whether the input was prime or not? (or how was that originally discovered? and did that discovery require simulation?)
Ultimately if the cortex uses approximate forward simulation, then we can’t do anything without some form of simulation.
This may come down to what you mean by simulate. Certainly a computer scientist would be unlikely to describe that as a simulation. And if you are asserting that anything with the same output as something else can be considered to be simulating it then your earlier claim becomes tautological. The then relevant issue becomes that this is an example where we can “simulate” something while using much less computation than running something is in complete detail (indeed, there’s very little resemblance in the internal workings).
I can prove things without simulating. One can look at code and determine what it does without simulating. The entire point of proving algorithms correct is that that’s done by mathematical proof, not by empirical testing for small values.
No, not correct.