3 ms·
> You can't compute fib(n) recursively with O(1) transistors. [...] There is no way I am aware of that could compute anything of recursive nature with a constan
by naasking 4y ago
> You can't compute fib(n) recursively with O(1) transistors. [...] There is no way I am aware of that could compute anything of recursive nature with a constant number of parts.
Every compute CPU in existence has a fixed number of transistors, so by this argument you can't compute fib(n) on any computer. In one sense this is technically correct because there is no bound on n, so you will encounter some n after which fib(n) will fail.
Obviously this is not what you meant though. The fixed number of parts is not the issue, it's whether they can be arranged to compute the function you want using the equilibrium behaviour you describe. Obviously this can be done if this equilibrium behaviour reproduces digital logic, so I'm not convinced it can't be done by in analog form, there just hasn't been a pressing need for it.
- 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.