Mathematics

Type-level Collatz Sequence

Implementing the famous Collatz conjecture entirely within TypeScript’s type system, demonstrating type-level arithmetic and recursive computation. The sequence follows $n \rightarrow n/2$ if even, $n \rightarrow 3n+1$ if odd, conjecturing all positive integers reach 1. Using template literal types and conditional type recursion, we can compute Collatz<27> yielding the 111-step sequence purely at compile time - pushing TypeScript’s type system to perform actual mathematical computation.

Programs of Length N: Collatz, Chaitin, and Church

How many lambda calculus programs exist with exactly $N$ terms? This exploration dives into deep questions about computational complexity, from counting programs like (λx. x x) (λx. x x) to analyzing the non-computable BB(N) busy beaver function that grows faster than any computable sequence. We examine Chaitin’s constant $Ω$ and why determining program convergence connects to unsolved problems like the Collatz conjecture collatz(3n + 1).