Maybe the input box uses its own notation, something weak enough that infinite loops are impossible but powerful enough to express Conway’s arrows? That seems like it would be enough to be interesting without accidentally adding a halting oracle.
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?
Would BlooP allow for chained arrow notation, or would it be too restrictive for that?
Sadly, you need more than that: chained arrows can express the Ackermann function, which isn’t primitive recursive. But I guess you don’t really need them. Even if you just have Knuth’s up-arrows, and no way to abstract over the number of up-arrows, you can just generate a file containing two threes with a few million up-arrows sandwiched between them, and have enough compute for most purposes (and if your program still times out, append the file to itself and retry).
Maybe the input box uses its own notation, something weak enough that infinite loops are impossible but powerful enough to express Conway’s arrows? That seems like it would be enough to be interesting without accidentally adding a halting oracle.
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?
Sadly, you need more than that: chained arrows can express the Ackermann function, which isn’t primitive recursive. But I guess you don’t really need them. Even if you just have Knuth’s up-arrows, and no way to abstract over the number of up-arrows, you can just generate a file containing two threes with a few million up-arrows sandwiched between them, and have enough compute for most purposes (and if your program still times out, append the file to itself and retry).