Hacker News Reader

Comment by kilgnad | Hacker News Reader

People are talking about logic gates and computing. While these things are associated with electric circuits, strictly speaking, they don't have to be. It's sort of a separate domain all together.

For something strictly an electric circuit that uses recursion take a look at an op-amp: https://en.wikipedia.org/wiki/Operational_amplifier. Normal operation of an op amp basically involves a feedback loop which is the analog equivalent of recursion.

Basically anything with a feedback loop is recursion.

View on HN

I will respectfully disagree about opamp feedback loops being recursion. It is almost magical but I do not see any recursive nature in it.

You can't compute fib(n) recursively with O(1) transistors. Maybe if you use the non-recursive exponentiation formula.

Analog electronics is different from digital computation because it's not about inputs and outputs, cause and effect in the same manner. A circuit maintains an equilibrium between inputs and outputs. The input doesn't cause the output as the changing the output may affect the input.

Just a simple resistor is an example: is voltage or current the input to Ohm's law? Neither is.

Same with the opamp feedback loop. It looks like it feeds its output to the input and then repeats. But it doesn't, it just maintains the same relationship between them by pumping electrons from the power supply. Short circuit the output to ground and you will see the circuit load the input circuit more.

That said opamp circuits are very cool. The patent for negative feedback was rejected as "another perpetual motion machine". Yet it works and it works magically.

A (bad) opamp can be cobbled together from 4 or 5 transistors. Yet it can do, together with negative feedback: addition, subtraction, multiply by constant, integral, derivative, exponent and logarithm. Probably others too. Combine log, add, and exp and you have a multiplier.

But it won't do a Fibonacci, a factorial or the Ackermann function.

There is no way I am aware of that could compute anything of recursive nature with a constant number of parts. You need some form of memory ("space") and a method of repeating the same computation ("time") to qualify.

You certainly can build this kind of computer with digital, or even analog, circuits. But negative feedback in opamps is not it.

This is my contribution to the Sunday morning semantics debate on the nature of recursive computation.

With a delay line and an opamp adder you can in fact sort of loop-compute fib(n). It won't be recursion though, more like a direct forward loop.

Feeding own output to own inputs IS a definition of a recursion

I don't think so, recursion would be having another opamp in the feedback path, which in turn has yet another opamp in it's feedback path and so on.

Why function application instantiates new opamps?! Its one feeding itself

There's no function application in circuitry. See

> It looks like it feeds its output to the input and then repeats. But it doesn't, it just maintains the same relationship between them by pumping electrons from the power supply.

> There’s no function application in circuitry.

Why do you say that? Of course there is. It would be more accurate to say all circuitry is built out of function applications, both analog and digital. If you can write an equation for the voltage on a given trace, the circuit applies a function. If you can write a truth table for a given component, that’s a function applicator. The whole reason we can build software functions is because we build them on top of circuit functions. Saying feedback doesn’t exist because it’s just electrons is like saying people are just atoms; it ignores the structure of the system. While all electric circuits pump electrons, signal feedback is a physical reality, one that you can even see & hear first-hand in some circuits. The OP maybe forgot momentarily to think about capacitors and time-varying inputs when they claimed analog circuits don’t have a time component.

For context I'm talking about function application a la lambda calculus. In this case 'function application' is something that's done to discrete symbols. Circuits aren't a discrete system however so there's no mapping.

Functions are a good way to describe things but it's not what they are fundamentally. OP also made a good point about how the inputs can change with the outputs but it's not recursive. It's literally the same process as water flowing more slowly into a lake as the lake gets more full. My intuition with circuits is that you'll end up doing something like that if you try to feed the output to the input without an intermediary store like a delay line or capacitor. And even then it's not recursive unless the algorithm you're running is tail optimized.

> Circuits aren’t a discrete system however so there’s no mapping.

You need to qualify that as analog circuits. And they do accept a discrete mapping, you’re just asserting without trying it.

> Functions are a good way to describe things but it’s not what they are fundamentally.

Yes it is. It is both how and why we build circuits; to apply the function’s effect, to pass it to the next function to build a larger function.

Why are you suddenly ruling out capacitors and delay lines? Those are analog circuitry, and they are absolutely standard building blocks.

> it’s not recursive unless the algorithm you’re running is tail optimized.

What’s wrong with tail optimized? That is still recursive, and it’s still feedback. You’re moving the goal posts. Above you and OP stated feedback (tail-recursion) was not a thing in analog circuits. That’s not true.

> You’re moving the goal posts.

To my credit the goalposts were never defined.

> You need to qualify that as analog circuits.

No, I don't. The context always has been analog circuits. OP makes the distinction here

> Analog electronics is different from digital computation because it's not about inputs and outputs, cause and effect in the same manner.

Good faith needs to be established before I continue, sorry

Oh sorry I was referring to the goal posts you defined with “There’s no function application in circuitry”, and repeating the OP’s claim that what looks like feedback actually isn’t feedback because circuits are in a static electric balance (which is not generally true for analog circuits).

Okay, I accept that the context was analog circuits, that’s fair, and I apologize for accidentally ticking you off with that note. I didn’t mean to, and I felt like a broad generalization could use the qualification, and all it needs is a single word. But I don’t see how that side-comment amounts to bad faith about anything, nor do I agree with that assessment. I’m arguing directly and with evidence against the claims you made, not with hyperbole, not with ad-hominem, but with facts: analog circuits with feedback are not just something that exists, they are widespread and common. Power conditioners, frequency filters, analog guitar delay pedals, all of these things are real-world counter-examples to the way OP framed it, and the way you defended that claim.

I'll be honest I wasn't meaning to defend OP's claim to the death or anything. I was mostly tracking their argument. I too am somewhat confused as to why just feeding outputs to inputs isn't recursive. I think honestly this is most people's intuition and the burden of proof (and therefore the fun) lies on stating the opposite i.e. it's not recursive.

I say this is bad faith arguing because you're very clearly trying to get me to say that circuits can be recursive. If you were arguing in good faith you'd be OK with "moving goalposts", as long as new ones were agreeably defined.

In this case the goalposts seem to be: analog circuits, with no delay wires, capacitors what have you. Basically circuits with no state.

In this case the reasoning basically boils down to: you have to have at least a stack to do recursion. Stack is state.

Now obviously the world of circuits is much bigger than this and in fact includes all stacks by the Computers Are Circuits theorem you provided. But using that is too easy, there's no fun. Good faith arguing is for fun, bad faith arguing is for points

Oh hi, you’re still here!

> I say this is bad faith arguing because you’re very clearly trying to get me to say that circuits can be recursive.

What are you talking about? Yes I am, in fact, arguing that analog circuits can be recursive, contrary to the claim OP made and you appeared to defend for multiple comments in a row. It’s not called bad faith when I question and contradict your claim, it’s called a discussion, argument, or debate.

If you didn’t mean to defend it to the death, that begs the question of why you’re choosing to escalate this conversation into ad-hominem territory. If you’re confused as to why analog circuit feedback is recursive, that begs the question why you said “OP also made a good point about how the inputs can change with the outputs but it's not recursive.”

> If you were arguing in good faith you’d be OK with “moving goalposts”

FWIW, that is not true, and sneaking in changes to your claim is not a particularly good faith move. Nor is accusing someone of bad faith when they point it out. It’s rather amusing that accusations of bad faith are rarely if ever made in good faith; they can be recursive too, just like analog circuits!

You have made several broad generalizations about analog circuits and feedback that are not true, essentially claiming analog circuit feedback and recursion can’t exist, and then after that started qualifying it as if you weren’t talking about capacitors and tail recursion, which contradicts the earlier claim that circuits can’t be recursive. I don’t agree to your new goalposts, and I said so, they are not “agreeably defined”.

> In this case the goalposts seem to be: analog circuits, with no delay wire, capacitors what have you. Basically circuits with no state.

I don’t agree these are the goalposts, you’re arbitrarily excluding common analog components, and this is not what OP was claiming. If you exclude capacitors or any state, you’re manufacturing a meaningless point about a not very useful subset of analog circuits, and saying nothing about analog circuits in general. You never answered the question of why you’re choosing to arbitrarily exclude widely used and completely standard analog circuitry, nor why you didn’t state this before I started mentioning capacitors.

> In this case the reasoning basically boils down to: you have to have at least a stack to do recursion. Stack is state.

Not sure what you’re talking about here. Stack is a digital circuit concept, while analog circuits can and do have state. Like I said, analog circuits with feedback and recursion don’t just exist - they are widespread and common.

It seems like you're saying recursion is applying a sequence of functions to each other like f1(f2(f3(x))). This doesn't seem right to me -- it should be more like f(f(f(x)))

It’s a loop, not necessarily recursion

Loops are isomorphic to recursion

The patent for negative feedback was rejected as "another perpetual motion machine" - I’d never heard this! Do you have a reference so I can read more?

"Inventing the Negative Feedback Amplifier", IEEE Spectrum (Dec 1977)

https://wiki.epfl.ch/me412-emem-2020/documents/06501721.pdf

The difficulty with the patent office is on the last page.

I read about this story in Horowitz, Hill : "The Art of Electronics" chapter on negative feedback.

You can find an old edition freely available here: https://archive.org/details/TheArtOfElectronics/Vol-1/mode/1...

Ofcourse an electric circuit cannot be «recursive» as such, because the physical ontology in which they are defined does not admit mereological (part/whole) relations, that would be «spooky action at a distance».

The signal function, being an interpretation (or specification) of the circuit, is a metaphysical ontology and is often defined in terms of itself at adjacent points in it’s domain, i.e mereological in nature, which is to say: recursive.

> 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.

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

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! ;)

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.

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.

> 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.

> 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.

Right, 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.

As long as a system can be defined in terms of itself it fits the definition of recursion if we are to follow the official definition of recursion.

Whether that recursion is capable of doing certain things is another matter entirely.

This is a semantic issue. Not worth it to get to deep into how I define a word or how you define a word. But I will say that my definition of the word recursion is more inline with the official definition, and that official definition does encompass an opamp.

Source: https://en.m.wikipedia.org/wiki/Recursion (see first sentence)

> There is no way I am aware of that could compute anything of recursive nature with a constant number of parts.

Computers have a constant number of parts, and also can’t compute arbitrary recursive functions - they run out of space.

Just define an escape condition, like do "recursions until we reach zero". I don't think recursion has to be infinite? One example is tail-recursion which can be statically defined by a compiler.

Resonant filters, like the classic Moog ladder filter, are another great example of recursive/feedback circuit designs.

As someone coming from a computing background, it always seems magical how the recursion in these types of analogue circuits happens instantaneously.

> how the recursion in these types of analogue circuits happens instantaneously.

Yeah, theoretically instantaneous, in practice not. (There's a measure for that but I can't remember how's it called)

Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.

>There's a measure for that but I can't remember how's it called Slew rate for opamps I believe

Also worth noting that the "recursion" without negative feedback will hit a limit when the op-amp is saturated. Similar to a "stack overflow" I guess. Things mostly won't break but you'll get a flat output at the positive or negative rails of the op-amp - which causes some of the pain of analog signal processing.

>Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.

The reason for this is because of how bandwidth is defined, which is basically the point at which the amplifier gain starts dropping the higher the frequency you go.

Adding feedback is effectively clipping the low frequency/ high gain area with the net effect that the gain versus frequency plot is a lot flatter (but now, instead of being able to get say 10,000x gain at 1Hz, you're clipping it to 100x, since you're unable to get 10,000x at 1Mhz)

It's not recursive. To be recursive you'd have to be able to unwind some sort of memory to get all previous states.

I don't think that's required for recursion. You only need access to as many previous states as you need for the result, but not all. We often talk about tail recursion optimisation where the stack never grows.

the unwinding property comes from the stack; see tail recursion

You can implement binary search recursively, which doesn’t care about the stack just the final iteration. I don’t see where the stack unwinding is necessarily for “call the same function inside itself unless you’re done” except in cases where the stack is used to compute a final answer that’s based on the prior iterations. Maybe it’s fair to say those would best be implemented iteratively, but it’s unnecessary that they be.

No matter how hard I try, I can't get this stupid snake to stop eating itself!

Feedback systems are iteration, not recursion: you can't go backwards.

(Tail recursion is I suppose recursion that only goes forwards and is considered equivalent to iteration?)

Iteration+state is equivalent to recursion. Simple feedback circuits can probably do primitive recursion, and for more powerful form of loops/recursion, you probably need to add stateful elements.

"anything with a feedback loop is recursion"

No. Recursion and feedback are absolutely different concepts.

i am trying to untangle the semantics of recursion/iteration/loop/feedback scientifically (that’s why i posted this link); do you have any sources?

https://en.m.wikipedia.org/wiki/Recursion

Anything that can be defined in terms of itself is recursion. This is the official definition and an opamp fits here.

A lot of people are getting lost in the variations of the semantics like computer recursion vs. analog recursion. I think the first sentence in the Wikipedia article, however, cinches the the general concept.

Yes anything with a feedback loop is recursion because a system with feedback is a system defined in terms of itself.

But these things in the end are semantic illusions. We are wasting huge amounts of effort in defining the boundaries of the definitions behind meaningless symbols.

Does the definition of banana encompass a rotten banana? Is something that has been rotted or digested... Is that still a banana? Who cares. Words are just used for communication. If your point was expressed properly without the need to clearly specify exact semantic definitions then I would just leave it at that.

Reply on news.ycombinator.com