It takes 829 bits of binary lambda calculus to interpret BrainFuck, which is very simple programming language modeled after Turing Machines. A self-interpreter

It takes 829 bits of binary lambda calculus to interpret BrainFuck, which is very simple programming language modeled after Turing Machines. A self-interpreter in BrainFuck takes well over a thousand bits though [2]. Lambda calculus is not only very simple, but also very expressive. While combinatory logic, with only S and K, is even simpler than lambda calculus, and also has a trivial binary encoding (00 for S, 01 for K, and 10 for application), the shortest known self-interpreter is 263 bits, appreciably larger than for lambda calculus. My IOCCC entry [3] has more examples of the conciseness of binary lambda calculus. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Brainfuck https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... [2] https://arxiv.org/html/cs/0311032 https://arxiv.org/html/cs/0311032 [3] http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html