3 ms·
I'll give it a try at defining the author's intuition of "doesn’t cheat" in the sense that it is always "making real progress". I'll define it as every intermed
by kccqzy 8y ago
I'll give it a try at defining the author's intuition of "doesn’t cheat" in the sense that it is always "making real progress". I'll define it as every intermediate value that is generated in the computation is eventually consumed. If a function, say, computes Ackermann(5,5) and throws away the result and then starts the actual sorting process, then the Ackermann(5,5) is unused and would be considered cheating. In a sense we can draw a data-flow diagram of the computation and everything has at least one outgoing edge, except perhaps the final output.
- XMPPwocky 8y agoProblem is we can define a function mix(a, b) which intermingles two arguments and produces a new value dependent on both- for example, sha256(a.concat(b)). Then we can take any randomized algorithm and, for its random values, use mix(real_rng.random(), Ackermann(5, 5)).