[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)