De Bruijn index
De Bruijn index is an alternative method to represent lambda calculus expressions.
Its attendant Busy Beaver problem is BBλ_db which uses De Bruijn index instead of binary to evaluate lambda calculus expression size. To calculate size, convert the lambda calculus expression into De Bruijn index, then count the number of backslashes (lambdas) and numbers. By example, (\1 1) (\\2 (1 2)) is size 8 because it has 3 backslashes and 5 numbers.
For n < 7, BBλ_db(n) = n is trivial and can be achieved via picking any size n term already in normal form, like BBλ(m) for m ≤ 20.
| BBλ_db(n) | Value | Champion | Discovered By |
|---|---|---|---|
| 7 | ≥ 7 | \1 1 1 1 1 1
|
|
| 8 | ≥ 16 | (\1 1) (\\2 (1 2))
|
Azerty & John Tromp & Bertram Felgenhauer |
| 9 | ≥ 68 | (\1 1) (\\2 (2 (1 2)))
|
John Tromp & Bertram Felgenhauer |
| 10 | (\1 1 1) (\\2 (2 (2 1)))
|
||
| 11 | (\1 1 1 1) (\\2 (2 (2 1)))
|
||
| 12 | (\1 1 1) (\1 (\\2 (2 1)) 1)
|
mxdys and racheline | |
| 13 | (\1 1) (\1 (\1 (\\2 (2 1)) 2))
|
mxdys | |
| 14 | (\1 1 1) (\\1 (1 2) (\\2 (2 1)))
|
50_ft_lock | |
| 15 | (\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))
|
Gustavo Melo | |
| 18 | (\1 1 1) (\1 (1 (\\\1 3 2 (\\2 (2 1)))))
|
50_ft_lock | |
| 22 | (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
|
Patcail | |
| 23 | (\1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
|
Patcail | |
| 24 | (\1 1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
|
Patcail | |
| 25 | (\1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))
|
Patcail | |
| 26 | (\1 1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))
|
Patcail |