If some function g is computable in O(f(n)) time for primitive recursive f then g is primitive recursive, by simulating a Turing machine. I am pretty sure a logical inductor would satisfy; while it’s super exponential time, it’s not so fast-growing it’s not primitive recursive (like with the Ackerman function).
If some function g is computable in O(f(n)) time for primitive recursive f then g is primitive recursive, by simulating a Turing machine. I am pretty sure a logical inductor would satisfy; while it’s super exponential time, it’s not so fast-growing it’s not primitive recursive (like with the Ackerman function).