2 ms·

> Analog [is] not about inputs and outputs [...] A circuit maintains an equilibrium between inputs and outputs. Capacitors provide memory and time-varying beha

by dahart 4y ago

> Analog [is] not about inputs and outputs [...] A circuit maintains an equilibrium between inputs and outputs. Capacitors provide memory and time-varying behavior. That’s one thing I’m sure you just forgot about for a minute. There are analog A/V circuits all around the world that explicitly feed back to themselves, thus in a sense explicitly computing a recursive function. > There is no way I am aware of that could compute anything of recursive nature with a constant number of parts. You’re forgetting about tail-recursion. In addition, a stack is still a constant number of parts (all computers & digital circuits have a recursion limit), and circuits are perfectly capable of repeating the same computation, even analog ones, so they qualify there at least.

marmetio 4y ago
Inductors too. In a state-space model, capacitances and inductances are the state variables.
- dahart 4y ago
  Indeed - the capacitor and the inductor go together like peanuts and chocolate. Maybe try to find an electronic device you own that doesn’t have an LC circuit in it! ;)
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 ago
  Yes, 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.

by dahart 4y ago

marmetio 4y ago

Inductors too. In a state-space model, capacitances and inductances are the state variables.

dahart 4y ago
Indeed - the capacitor and the inductor go together like peanuts and chocolate. Maybe try to find an electronic device you own that doesn’t have an LC circuit in it! ;)

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 ago
Yes, 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.