This is surprisingly approachable. It's fun (and flattering, I suppose) to see computability explained in a broader context.
It makes me wonder: what is the lambda-calculus equivalent of the busy beaver? Number of normal-order steps before normalization (for a given program size)? Are the LCBB numbers different for different evaluation orders? What metric do you use for program size: depth? Number of lambdas?
1 comment
[ 3.3 ms ] story [ 10.8 ms ] threadIt makes me wonder: what is the lambda-calculus equivalent of the busy beaver? Number of normal-order steps before normalization (for a given program size)? Are the LCBB numbers different for different evaluation orders? What metric do you use for program size: depth? Number of lambdas?