Hacker News Reader

This is the first time I read about his NPRNPR distillation of Gödel's proof (N=Not,P=Provable,R=Repeat). So clever. And so Smullyan.

I'll always remember his https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird as a most delightful introduction to Combinatory Logic.

View on HN

Funny enough, a similar trick can be used to give you the Y combinator.

Let comp be the 'compose' combinator

((comp f g) x) = (f (g x))

Let R be the 'repeat' or 'self-application' combinator

(R x) = (x x)

Then (Y f), the combinator obeying the equation

(Y f) = (f (Y f))

can be expressed as

(Y f) = (R (comp f R))

If our f is NP, then we'll have (NP (R (comp NP R))). So, in other words, NPRNPR is just (Y NP).

Funny enough, taking that definition of the Y combinator, you can get all of its special forms (normal order, applicative order, and polyvaradic normal & applicative order), just by changing the definition of the 'comp' function.

Here's a gist that shows how:

https://gist.github.com/mromyers/b6d7678bf7a04e106b3d7d5b649...

Then you must not miss his book "Satan, Cantor, and Infinity."

For the benefit of those skimming the comments and not reading TFA: https://amzn.to/2SvmTdX (affiliate link).

Reply on news.ycombinator.com