4 ms·
Capacitors and inductors are "memory" but only one unit or "word" per component. You need more than one to make a stack to have recursion. Mercury delay lines,
by exDM69 4y ago
Capacitors and inductors are "memory" but only one unit or "word" per component. You need more than one to make a stack to have recursion.
Mercury delay lines, neon bulbs, magnetic drums or disks and lots of other components are also capable of storing a quantity for some time.
Tail recursion is just a loop, and we certainly can do simple repetition in a circuit.
I'm not arguing that you can't build a digital or analog computer capable of recursion, you certainly can but it takes O(n) components where n is recursion depth.
But I am arguing that a feedback loop in an opamp circuit is not a form of recursion. It is not capable of computing the Ackermann function or any other recursive function, which I consider the smoke test here.
- dahart 4y agoYes, some recursion can be implemented in a loop. Op-amp feedback, and analog audio delays, just for two examples certainly are a valid subset of real recursion, the kind that only recurse once, as opposed to two or more times. It is a form of recursion, so I still disagree with your argument. Note the actual question explicitly stated that tail-recursion is in-bounds. The Ackermann function recurses twice, so yes it would need some kind of memory, which could theoretically be implemented with an analog stack of some kind. And I agree that loop-based (single recuse) op-amp feedback can’t compute Ackermann, but the question was whether recursion is possible in analog circuits, and the answer is that single-recurse already exists widely, and double recurse or more could be done by someone determined, there’s no theoretical constraint.