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).
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).