logoalt Hacker News

orlpyesterday at 10:03 PM1 replyview on HN

An interesting follow-up question is, what is the smallest number unable to be encoded in 64 bits of binary lambda calculus?


Replies

trompyesterday at 10:11 PM

BLC can output any literal 60 bit string x as the 64-bit (delimited) program 0010 x, so in that sense it would be some 61 bit number. But if ask about just lambda calculus terms without the binary input, then I think it would be some small number of at most 10 bits. BBλ looks at the normal form size so it cannot even reach numbers 0,1,2,3, and 5.