https://wiki.bbchallenge.org/w/index.php?action=history&feed=atom&title=De_Bruijn_index
De Bruijn index - Revision history
2026-05-10T01:31:41Z
Revision history for this page on the wiki
MediaWiki 1.43.5
https://wiki.bbchallenge.org/w/index.php?title=De_Bruijn_index&diff=7490&oldid=prev
ADucharme: creation of page by taking section from lambda calculus page
2026-05-09T23:01:00Z
<p>creation of page by taking section from lambda calculus page</p>
<p><b>New page</b></p><div>'''De Bruijn index''' is an alternative method to represent lambda calculus expressions. <br />
<br />
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 [[wikipedia:De_Bruijn_index|De Bruijn index]], then count the number of backslashes (lambdas) and numbers. By example, <code>(\1 1) (\\2 (1 2))</code> is size 8 because it has 3 backslashes and 5 numbers.<br />
<br />
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.<br />
{| class="wikitable"<br />
!BBλ_db(n)<br />
!Value<br />
!Champion<br />
!Discovered By<br />
|-<br />
|7<br />
|≥ 7<br />
|<code>\1 1 1 1 1 1</code><br />
|<br />
|-<br />
|8<br />
|≥ 16<br />
|<code>(\1 1) (\\2 (1 2))</code><br />
|[[User:Azerty|Azerty]] & John Tromp & Bertram Felgenhauer<br />
|-<br />
|9<br />
|≥ 68<br />
|<code>(\1 1) (\\2 (2 (1 2)))</code><br />
|John Tromp & Bertram Felgenhauer<br />
|-<br />
|10<br />
|<br />
|<code>(\1 1 1) (\\2 (2 (2 1)))</code><br />
|<br />
|-<br />
|11<br />
|<br />
|<code>(\1 1 1 1) (\\2 (2 (2 1)))</code><br />
|<br />
|-<br />
|12<br />
|<br />
|<code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code><br />
|mxdys and racheline<br />
|-<br />
|13<br />
|<br />
|<code>(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code><br />
|mxdys<br />
|-<br />
|14<br />
|<br />
|<code>(\1 1 1) (\\1 (1 2) (\\2 (2 1)))</code><br />
|50_ft_lock<br />
|-<br />
|15<br />
|<br />
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code><br />
|Gustavo Melo<br />
|-<br />
|18<br />
|<br />
|<code>(\1 1 1) (\1 (1 (\\\1 3 2 (\\2 (2 1)))))</code><br />
|50_ft_lock<br />
|-<br />
|22<br />
|<br />
|<code>(\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))</code><br />
|Patcail<br />
|-<br />
|23<br />
|<br />
|<code>(\1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))</code><br />
|Patcail<br />
|-<br />
|24<br />
|<br />
|<code>(\1 1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))</code><br />
|Patcail<br />
|-<br />
|25<br />
|<br />
|<code>(\1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))</code><br />
|Patcail<br />
|-<br />
|26<br />
|<br />
|<code>(\1 1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))</code><br />
|Patcail<br />
|}</div>
ADucharme