3 ms·
> that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop
by ogogmad 6y ago
> that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts)
The primitive recursive functions cannot be expressed using circuits. Circuits by definition can only express polynomials, which have a much smaller growth rate than what primitive recursive functions are capable of.
[edit]
Actually, probably a better reason is that in primitive recursion, the running time can depend on the input. For a circuit, the running time is independent of the input.
- extropy 6y agoThe circuit that repeatedly multiplies the previous result with itself has higher than exponential growth rate.
- ogogmad 6y agoNo, because you can only multiply a fixed number of times.
- lalaland1125 6y agoGood luck finding something that grows faster than https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function
- suyjuris 6y agoEasy, just square it. Also, the Ackermann function is not a primitive recursive function.