3 ms·

The lower bound on the information content of a string is the length of the shortest program that can output the string (and halt), this is called its Kolmogoro

The lower bound on the information content of a string is the length of the shortest program that can output the string (and halt), this is called its Kolmogoroff complexity. Lambda calculus is (one of) the most compact ways to encode programs and requires the least context to interpret. Thus it’s totally fair to say that the largest number encoded in LC in some number of bits is much more fundamental and less arbitrary a candidate than just randomly deciding that "1" now refers to some externally defined large number.

eru 3y ago
Something like SKI calculus seems a lot less arbitrary than lambda calculus in terms of representation, perhaps.
- chriswarbo 3y ago
  The author has also implemented Binary Combinatory Logic. I also find combinators more "natural" than lambda calculus (although the latter is certainly more useful day-to-day!); however, I still find lambda calculus a reasonable foundation since the Binary Lambda Calculus self-interpreter is shorter than the Binary Combinatory Logic self-interpreter (e.g. see the author's page at http://tromp.github.io/cl/cl.html http://tromp.github.io/cl/cl.html )
  - eru 3y ago
    Writing programs in lambda calculus is definitely more enjoyable than in eg SKI calculus. I think if you express your lambda calculus bindings in terms of De Bruijn indices, it might seem less arbitrary, too.
  - MadnessASAP 3y ago
    I don't think your day and my day are quite the same.
    - chriswarbo 3y ago
      Lambda calculus is present in most "modern" programming languages, i.e. those which use lexical scope rather than global or dynamic scope; and those which call functions to return results (especially first-class functions) rather than jumping to subroutines for their effects. It's why Python functions are written with the keyword `lambda`, and it's why Amazon's function-as-a-service product is called Lambda. For example, say you're refactoring some code and come across: def foo(x): return bar(x) You decide to simplify this definition to: foo = bar Congratulations, you've just performed η-reduction! https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reduction https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reducti...
      - eru 3y ago
        As an aside: alas, η-reduction is not something that's properly supported in Python.

eru 3y ago

Something like SKI calculus seems a lot less arbitrary than lambda calculus in terms of representation, perhaps.

chriswarbo 3y ago
The author has also implemented Binary Combinatory Logic. I also find combinators more "natural" than lambda calculus (although the latter is certainly more useful day-to-day!); however, I still find lambda calculus a reasonable foundation since the Binary Lambda Calculus self-interpreter is shorter than the Binary Combinatory Logic self-interpreter (e.g. see the author's page at http://tromp.github.io/cl/cl.html http://tromp.github.io/cl/cl.html )
- eru 3y ago
  Writing programs in lambda calculus is definitely more enjoyable than in eg SKI calculus. I think if you express your lambda calculus bindings in terms of De Bruijn indices, it might seem less arbitrary, too.
- MadnessASAP 3y ago
  I don't think your day and my day are quite the same.
  - chriswarbo 3y ago
    Lambda calculus is present in most "modern" programming languages, i.e. those which use lexical scope rather than global or dynamic scope; and those which call functions to return results (especially first-class functions) rather than jumping to subroutines for their effects. It's why Python functions are written with the keyword `lambda`, and it's why Amazon's function-as-a-service product is called Lambda. For example, say you're refactoring some code and come across: def foo(x): return bar(x) You decide to simplify this definition to: foo = bar Congratulations, you've just performed η-reduction! https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reduction https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reducti...
    - eru 3y ago
      As an aside: alas, η-reduction is not something that's properly supported in Python.