4 ms·
Those computers with rich instruction sets are built up of smaller units made of smaller units, down to individual transistors (typically 2 kinds). It's pretty
by tlb 4y ago
Those computers with rich instruction sets are built up of smaller units made of smaller units, down to individual transistors (typically 2 kinds). It's pretty cool that you can build something so complex from a couple types of components and wires.
Lambda calculus is the analogous building block for algorithms. With just a few primitives (including the Y combinator) you can have a powerful system upon which you can build any (no-quantum) algorithm at all.
I find it deeply pleasing that all our fancy systems can be broken down to such simple components, and I'm glad to belong to the profession of people who are good at this task.
- lou1306 4y agoBut the cool part is that the YC is not actually a primitive. Primitives in lambda calculus are essentially just variables, function definition, and application. At a first glance, you wouldn't tell that you could express infinite computation from such rudimentary tools, but the YC shows that you actually can.