Mathematics

The Collatz conjecture is an unsolved problem in mathematics. It states that for any positive integer n, the sequence of numbers generated by the following algorithm will eventually reach 1. These are also called the hailstone numbers. function collatz(n: number): number { return n % 2 === 0 ? n / 2 : 3 * n + 1; } The sequence generated by a given $n$ is the sequence of numbers n, collatz(n), collatz(collatz(n)), collatz(collatz(collatz(n))), and so on.

There are a few interesting questions about the nature of programs, and specifically about sets of programs, as represented by lambda calculus expressions. 1. How many programs have N terms? 2. How fast does the set of programs of length N grow? 3. How many programs of length N converge? 4. What is the longest-running convergent program of length N? 5. How fast does BB(N) grow? 6. What percentage of programs converge?