How exactly does the “speed” box take input? Because if its input is a plain decimal number, then we really only have access to exponential compute, since we’ll need to type out a string of n digits to get 2^O(n) compute. If takes more general programs (which output a number), then we can use the machine itself to search for short formulas which output large numbers, which might buy us a lot more compute. On the other hand, if the speed box takes general programs, then it needs to somehow recognize programs which don’t halt, which we could also exploit for hypercomputation.
I’ll go with Taran’s idea there, I think. Something like Douglas Hofstadter’s BlooP language, perhaps, which only allows primitive recursive functions. Would BlooP allow for chained arrow notation, or would it be too restrictive for that? More generally, what is the fastest growing primitive recursive function possible, and what limits would that give us in terms of the scope of problems that can be solved by our magic box?
that’s a really good point, and I’m mentally kicking myself right now for not having thought of that. In answer to another comment below yours, I suggested only allowing primitive recursive functions to be entered as input in the second box, which I think would solve the problem (if possibly creating another computational limit at the growth rate of the fastest growing primitive recursive function possible [which I haven’t studied at all tbh, so if you happen to have any further reading on that I’d be quite interested]). Going a bit further with this, while I suggested God limiting us to one bounded language like BlooP to use on the second field, if He instead allowed for any language to be used, but only primitive recursive functions to be run, would we be able to exploit that feature for hypercomputation?
Also, while we’re discussing it, what would be in the space of problems that could be uniquely solved by 2^O(n) compute, but not by “normal” O(n) compute?
Yeah, that makes sense.
How exactly does the “speed” box take input? Because if its input is a plain decimal number, then we really only have access to exponential compute, since we’ll need to type out a string of n digits to get 2^O(n) compute. If takes more general programs (which output a number), then we can use the machine itself to search for short formulas which output large numbers, which might buy us a lot more compute. On the other hand, if the speed box takes general programs, then it needs to somehow recognize programs which don’t halt, which we could also exploit for hypercomputation.
-
I’ll go with Taran’s idea there, I think. Something like Douglas Hofstadter’s BlooP language, perhaps, which only allows primitive recursive functions. Would BlooP allow for chained arrow notation, or would it be too restrictive for that? More generally, what is the fastest growing primitive recursive function possible, and what limits would that give us in terms of the scope of problems that can be solved by our magic box?
that’s a really good point, and I’m mentally kicking myself right now for not having thought of that. In answer to another comment below yours, I suggested only allowing primitive recursive functions to be entered as input in the second box, which I think would solve the problem (if possibly creating another computational limit at the growth rate of the fastest growing primitive recursive function possible [which I haven’t studied at all tbh, so if you happen to have any further reading on that I’d be quite interested]). Going a bit further with this, while I suggested God limiting us to one bounded language like BlooP to use on the second field, if He instead allowed for any language to be used, but only primitive recursive functions to be run, would we be able to exploit that feature for hypercomputation?
Also, while we’re discussing it, what would be in the space of problems that could be uniquely solved by 2^O(n) compute, but not by “normal” O(n) compute?