Hacker GitHub

← All repos

tromp/AIT

View on GitHub ↗ ★ 213 Haskell

Algorithmic Information Theory, using Binary Lambda Calculus

27 mentions on Hacker News by 3 people: 0 stories, 27 comments · first 2016-05-04 · latest 2026-09-30

Mentions per year 27 mentions · busiest year 2025 (7)
20082026
AllStoriesComments NewestTopOldest
  1. …which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm. [1] https://github.com/tromp/AIT/blob/master/uni.c
    comment by tromp · 2026-09-30 · in Needed 1+1, built a functional programming language
  2. …[3]=++C+u:exit(6) )e=L[C++],u=L[C];} while a less obfuscated and highly performant implementation https://github.com/tromp/AIT/blob/master/uni.c based on combinatory graph reduction takes 446 lines.
    comment by tromp · 2026-05-11 · in 7 lines of code, 3 minutes: Implement a programming language (2010)
  3. …t.github.com/tromp/86b3184f852f65bfb814e3ab0987d8... [3] https://tromp.github.io/cl/diagrams.html [4] https://github.com/tromp/AIT/blob/master/ait/int.lam
    comment by tromp · 2026-05-11 · in 7 lines of code, 3 minutes: Implement a programming language (2010)
  4. …between functions and numbers, and in this case no additional constant (like 1) is needed. [1] https://github.com/tromp/AIT/blob/master/ait/minbase.lam
    comment by tromp · 2026-04-13 · in All elementary functions from a single binary operator
  5. …proofs in the Calculus of Constructions to demonstrate [2] that BBλ(1850) > Loader's Number. [1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co... [2] https://codegolf.stackexchange.com/questions/176966/golf-a-n...
    comment by tromp · 2026-03-22 · in A case against currying
  6. …│ └─┤ │ │ │ │ │ │ │ ├─┘ │ │ │ │ │ ├───┘ │ │ │ │ ├─┘ │ │ │ └───┤ │ │ │ └─────────┤ │ │ └─┤ │ └─┘ [1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
    comment by tromp · 2025-11-23 · in Almost all Collatz orbits attain almost bounded values
  7. …(K f). These tuple numerals are useful in proving lower bounds on a functional busy beaver [2]. [1] https://github.com/tromp/AIT/blob/master/numerals/tuple_nume... [2] https://oeis.org/A333479 (see bms.lam link)
    comment by tromp · 2025-11-16 · in De Bruijn Numerals
  8. …interpreter [3]. [1] https://tromp.github.io/cl/LC.pdf [2] https://www.ioccc.org/2012/tromp/ [3] https://github.com/tromp/AIT/blob/master/uni.js#L56
    comment by tromp · 2025-10-23 · in Programming with Less Than Nothing
  9. Simple pure concatenative languages map quite well though [1]. [1] https://github.com/tromp/AIT/blob/master/ait/mlatu.lam
    comment by tromp · 2025-10-20 · in Forth: The programming language that writes itself
  10. …the so-called Bashicu Matrix System) to be expressed in only 350 bits rather than 404 bits. [2] [1] https://github.com/tromp/AIT/blob/master/numerals/tuple_nume... [2] https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
    comment by tromp · 2025-09-24 · in The Lambda Calculus (2023)
  11. …we can use additional combinators and rules to speed things up (good example is clapp() function in https://github.com/tromp/AIT/blob/master/uni.c ). Of course, the extra rules have to be logically consistent with the base S and K…
    comment by js8 · 2025-06-25 · in The bitter lesson is coming for tokenization
  12. …that youtuber CodeParade made about the Quest To Find The Largest Number and its followup [3]. [1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co... [2] https://codegolf.stackexchange.com/questions/176966/golf-a-n... [3]…
    comment by tromp · 2025-04-05 · in Loader's Number
  13. …to short universal lambda expressions (each can be expressed as combinators) of this type: https://github.com/tromp/AIT/blob/master/Bases.lhs
    comment by js8 · 2024-12-10 · in Tree Calculus
  14. …Graham’s Number was found more recently: (λJ.J J) (λy.y (y (λg.λm.m g (λf.λx.f (f x))))) [1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
    comment by tromp · 2024-06-14 · in Lambda Calculus Interpreter
  15. …(λ λ 1 2 (λ 1)) (λ λ 5 (2 1)) 3) 1) (λ λ 2 (3 2 1))) (λ λ 2 (2 (2 1))) of Graham's number [1]. [1] https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
    comment by tromp · 2024-04-20 · in Church's λ-Calculus (2023) [pdf]
  16. Acutally, I only learned about the 49 bit program after writing that blog entry. It is described in https://github.com/tromp/AIT/blob/master/fast_growing_and_co...
    comment by tromp · 2024-04-14 · in Ray tracer in a boot sector
  17. …which is encoded as bit 0 (left branch), while bit 1 (right branch) encodes prefix application. [1] https://github.com/tromp/AIT/blob/master/ait/allA.lam
    comment by tromp · 2023-12-20 · in Does quantum theory imply the universe is preordained?
  18. …generates the characteristic sequence of primes [1] [2]. [1] https://tromp.github.io/cl/cl.html [2] https://github.com/tromp/AIT/blob/master/characteristic_sequ...
    comment by tromp · 2023-08-23 · in My favorite prime number generator
  19. I expect so, as the author is familiar with my tools [1] for doing these optimizations. [1] https://github.com/tromp/AIT
    comment by tromp · 2022-10-07 · in Show HN: Lambda-8cc – An x86 C compiler written in untyped lambda calculus
  20. …lambda calculus program, see this self-interpreter [1] for binary lambda calculus [2]. [1] https://github.com/tromp/AIT/blob/master/uni.lam [2] https://www.ioccc.org/2012/tromp/hint.html
    comment by tromp · 2022-05-24 · in Minimalism in programming language design
  21. …https://tromp.github.io/cl/Binary_lambda_calculus.html > https://www.ioccc.org/2012/tromp/hint.html > https://github.com/tromp/AIT
    comment by tromp · 2022-02-28 · in Lambda Calculus in 400 Bytes
  22. Build https://github.com/tromp/AIT and you can use ./blc Pbm foo.lam >foo.pbm; convert foo.pbm -interpolate Nearest -filter point -resize 800% foo.png
    comment by jart · 2022-02-28 · in Lambda Calculus in 400 Bytes
  23. …[2] https://tromp.github.io/cl/Binary_lambda_calculus.html [3] https://github.com/tromp/AIT/blob/master/int.lam
    comment by tromp · 2021-12-20 · in Show HN: Lisp with GC in 436 Bytes
  24. …ZFC [3]. I.e. it may or may not be unprovable, we don't know yet. [1] https://oeis.org/A333479 [2] https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-tab ...
    comment by tromp · 2021-12-05 · in The 8000th Busy Beaver number eludes ZF set theory (2016)
  25. …that potentially grows so much faster than Goodstein, that it's not even provable in ZFC [3]. [1] https://github.com/tromp/AIT/blob/master/goodstein.lam [2] https://github.com/tromp/AIT/blob/master/laver.lam [3]…
    comment by tromp · 2021-11-18 · in A Busy Beaver champion derived from scratch
  26. …describes a 27 state Goldbach checking TM, which takes no more than 378 bits to encode, while https://github.com/tromp/AIT/blob/master/goldbach.lam describes an equivalent 267 bit Lambda Calculus term, which can also be represented as this…
    comment by tromp · 2016-05-11 · in Turing machines that should run forever
  27. …a counterexample to Goldbach’s Conjecture" I constructed a 267 bit binary lambda term defined in https://github.com/tromp/AIT/blob/master/goldbach.lam and pictured in https://github.com/tromp/AIT/blob/master/goldbach.gif that normalizes…
    comment by tromp · 2016-05-04 · in The 8000th Busy Beaver number eludes ZF set theory