Binary Lambda Calculus

This article covers the uncomputable function OEIS A333479, known as BBλ. BBλ(n) is the size of the largest normal form of any normalizing closed lambda term of size n, where the size of a term is its length when encoded in BLC.

Summary

The following diagram summarizes known values and problems relative to BBλ.

Interval tree of gauge for BBλ

Tables of Values

Interp(BF)

SourceProgram Name/ParametersBBλ(n)
Felgenhauer & Tromp 2011ait/bf.lam829

Goldbach conjecture

SourceProgram Name/ParametersBBλ(n)
Felgenhauer 2013fast_growing_and_conjectures/goldbach.lam267

Goodstein's theorem

SourceProgram Name/ParametersBBλ(n)
Felgenhauer 2014fast_growing_and_conjectures/goodstein.lam351

Period 32 Laver table

SourceProgram Name/ParametersBBλ(n)
Felgenhauer & Tromp 2016fast_growing_and_conjectures/laver.lam213
Felgenhauer & Tromp 2016codegolf/laver.lam215

Odd perfect number

SourceProgram Name/ParametersBBλ(n)
Tromp 2020fast_growing_and_conjectures/oddperfect.lam247
Felgenhauer 2020fast_growing_and_conjectures/perfect.lam288

Interp(BLC)

SourceProgram Name/ParametersBBλ(n)
Felgenhauer & Tromp 2011ait/uni.lam232
Tromp 2024ait/uniK.lam975

Interp(BLC2)

SourceProgram Name/ParametersBBλ(n)
Tromp 2024ait/uni2.lam334

Interp(BLC2[8])

SourceProgram Name/ParametersBBλ(n)
Tromp 2024ait/uni28.lam500

Interp(BLC[8])

SourceProgram Name/ParametersBBλ(n)
Felgenhauer & Tromp 2011ait/uni8.lam355