3 ms·
This keeps popping up, and it is no more persuasive the tenth time than the first. Universal Computation was demonstrated a long time before Lisp. Any Turing-c
by ncmncm 6y ago
This keeps popping up, and it is no more persuasive the tenth time than the first.
Universal Computation was demonstrated a long time before Lisp. Any Turing-complete language is universal, Lisp included. Church's lambda calculus is included, and Lisp is a notation for lambda calculus. So, you can write a Lisp interpreter in Lisp, and it's pretty compact because (surprise!) a Lisp Interpreter has a lot of support for the stuff you need to do to Interpret Lisp. There's nothing deeply meaningful about it beyond what you start out with from Church.
It is much more impressive, and subtly meaningful, that a NAND gate is universal. You can build a machine that runs Lisp from nothing but NAND gates, and people have. There have even been commercially successful discrete-transistor mainframes made of practically nothing but NOR gates (plus core memory), which are identically universal.
Transistors are therefore universal. But because their operation is described in analog terms, they don't quite fit the mathematical formalism. The universe doesn't care about that, so it allows us to build up Universal Computation out of analog transistors. The more transistors you put in, the more computation you can do in a second.
- UK-Al05 6y agoI think transistors are great for electrical side of computing. Lambda calculus and lisp for the abstract model.
- tr352 6y agoYou're speaking of functional completeness of boolean operators which I think is quite unrelated to theories of computation. For computation you need some notion of state, and while a circuit made of logic gates may possess some notion of state, a logic gate in itself does not. As for transistors being universal (whatever that means) if this is true then vacuum tubes, relays, pneumatic valves, etcetera are also universal.