3 ms·
> Every compute CPU in existence has a fixed number of transistors, Fixed and very large number. It can compute fib(n) for a finite but large number n. Even wi
by exDM69 4y ago
> Every compute CPU in existence has a fixed number of transistors,
Fixed and very large number. It can compute fib(n) for a finite but large number n. Even with infinite time, my computer couldn't compute fib(2^128) recursively because there is not enough memory to store the stack.
You need O(recursion depth) memory, which implies number of components in the same order of magnitude.
- naasking 4y agoRight, but my point is that the component count scaling requirements for an analog circuit are basically the same, so of course you can compute fib(N) using analog circuitry. You can even do it using a fixed number of components, as long as the component count is large enough.