[HN Gopher] Binary Lambda Calculus ___________________________________________________________________ Binary Lambda Calculus Author : tosh Score : 42 points Date : 2022-11-09 20:52 UTC (2 hours ago) (HTM) web link (tromp.github.io) (TXT) w3m dump (tromp.github.io) | nonrandomstring wrote: | Gives me an "Agent Smith moment", just marvelling at its beauty, | it's genius. | zaik wrote: | A program in Binary Lambda Calculus to compute the Ackermann | function is less than 7 bytes: | https://codegolf.stackexchange.com/a/83924 | Ameo wrote: | > Roughly speaking, the complexity of an object is the length of | its shortest description. | | This has a ton of really interesting implications. | | Even though Kolmogorov complexity is technically incomputable due | to the halting problem, you can estimate it. One method of doing | that is to create a bunch of random Turing machines and see how | often they produce some output string[1]. You have to cut them | off after running for a while to prevent infinite loops but it | turns out that the output probability of a string strongly | correlates with its Kolmogorov complexity. | | This works for neural networks as well. You can treat a neural | network as a binary classifier, or more generally a boolean | function that has some number of binarized inputs mapping to a | single binary output. | | I explored this a bit in a blog post I wrote a while ago[2]. By | randomly initializing weights and counting the truth tables | produced, you can estimate Boolean complexity for different | expressions which is NP hard. | | [1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4014489/ | | [2] https://cprimozic.net/blog/boolean-logic-with-neural- | network... | irsagent wrote: | I assume you can simulate a turning machine with it. | tromp wrote: | I don't know about turning machines, but it can certainly | simulate Turing machines. You can even interpret Brainfuck, a | Turing Machine inspired esoteric language, in under 104 bytes | [1]. | | [1] | https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... | tromp wrote: | A BLC interpreter [1] won in the 2012 International Obfuscated C | Code contest [2]. | | BLC provides a functional busy beaver function [3] that is more | fine-grained than the TM-based one. | | The byte oriented version BLC8 is one of the 128 languages in the | quine relay [3]. | | [1] https://www.ioccc.org/2012/tromp/tromp.c | | [2] https://www.ioccc.org/2012/tromp/hint.html | | [3] https://oeis.org/A333479 | | [4] https://esoteric.codes/blog/the-128-language-quine-relay | 7373737373 wrote: | Related: Iota, Jot and Zot by Chris Barker: | | https://en.wikipedia.org/wiki/Iota_and_Jot | | http://cleare.st/code/iota-jot-zot | | > Every combination of 0's and 1's is a syntactically valid Jot | program, including the null program. | tromp wrote: | While these are very simple universal languages, as is a simple | binary language based on S K combinators (see Section 3.2 of | [1]), they don't yield the very compact programs that BLC does. | | [1] https://tromp.github.io/cl/LC.pdf ___________________________________________________________________ (page generated 2022-11-09 23:00 UTC)