Recursion

Advanced Logic Computation

One thing is conspicuously missing: loops. Functions have no names, so nothing can refer to itself — there is no f(...) where f can call f. And yet every real algorithm needs repetition. The fix is the most famous trick in the field.

The divergent term

Start with a paradox. What happens if a function eats itself?

Ω β-reduces to itself: an infinite loop in a single line. (The stepper will give up at its safety cap — it never reaches a normal form because there isn't one.)

Fixed points

A fixed point of a function g is a value X with g X = X. Now suppose a magic combinator Y exists with the property:

Feed Y a function that says "if n is zero, return 1, else multiply n by myself of n−1" — and the argument is the recursive call. Self-reference, built out of nothing but substitution.

The Y combinator

Notice the Ω trick inside: x x is self-application again, but this time wrapped in f (…) so each "loop" does one step of real work before recursing. Ω diverges; Y does something each round.

Factorial, in principle

Every piece on that line is something you built: IF, ISZERO, MULT from Church encodings, PRED (the hard one — it rides on pairs), and Y for the loop. No built-ins. No names. One rule.

Where next

• The wiki's Lambda calculus — the full deep read: history, equivalences, and the people
• Alonzo Church — the man at the blackboard
• Further reading & research — the primary sources

AdaLogic BASIC is kept by the ALB team — a family-friendly site for learning and sharing programs. Guidelines · Privacy · Terms · Trademarks · AI disclosure · Contact · Giants · Technology · IDE.