3 ms·
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
by tromp 8y ago
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 https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird as a most delightful introduction to Combinatory Logic.
- braythwayt 8y agoThen 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 https://amzn.to/2SvmTdX (affiliate link).
- mrmyers 8y agoFunny 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/b6d7678bf7a04e106b3d7d5b6493a2e7 https://gist.github.com/mromyers/b6d7678bf7a04e106b3d7d5b649...