cp's OEIS Frontend

A 1-closed term is a term in de Bruijn notation that is closed with 1 additional lambda in front. Any variable bound to that lambda is a free variable "f" in the term.

An oracle reduction step reduces f t, where t is a closed normal form of size s, to Church numeral BB(s).

The jump at a(14) is due to lambda term 1(1(\\1)). Subterm (1(\\1)) is an application of free variable f to a closed term of size 6 and thus oracle reduces to Church numeral BB(6) = C6. Next, (1 C6) is an application of free variable f to a closed term of size 36 and thus oracle reduces to Church numeral BB(36) = C(2^2^2^3) of size 6+5*2^2^2^3.

a(14) is also the last term that fits in this universe. Subsequent terms can be expressed in terms of function f(n) = 6+5*BB(n): a(15)=f(41) by 1(1(\\2)), a(16)=f(266) by 1(1(1(\1))), a(17)=f(51) by 1(1(\\\2)), a(18)=f^2(266) by 1(\1)1(\1), a(19)=f^2(41) by 1(1(1(\\2))), a(20)=f^4(266) by 1(\\1)1(\1), a(21)=f^5(266) by 1(\\2)1(\1), and a(22)=f^50(266) by 1(1(\1))1(\1).

a(28) >= f^BB(f^3(4))(4) by 1(\1)1(\1)1(\1).

a(29) >= f^{BB(f^{BB(f^4(4))+4}(4))+BB(f^4(4))+5}(4) by 1(\1)(\1 2 1)(\1).

This function is uncomputable even with access to a halting oracle.

We can generalize BB_1 to BB_a for ordinals a by using oracle function BB_{a-1} for successor ordinal a, and oracle function (\n -> BB_{a[n]}(n)) for limit ordinal a, assuming well-defined fundamental sequences up to a. Because of limited oracle inputs, all oracle busy beavers have identical values up to n=11.

This sequence is uncomputable, like the corresponding Busy Beaver sequence A333479, which takes the maximum normal form size of the a(n) terms that have one.

Self-delimiting BLC programs are inputs p to the BLC universal machine U (defined in first link) that make U read all bits of p and none beyond. Formally, the only prefix p' of p for which U(p':Omega) has a normal form is p itself. The output of p is that normal form.

This Busy Beaver is directly related to Kolmogorov Complexity: a(n) = max {size(x)| KP(x) = n }, where KP is the prefix Kolmogorov complexity (defined in first link).

Because programs for U are at most a constant number of bits longer than programs for any prefix-free programming language, this busy beaver is optimal: for any other busy beaver BB based on self-delimiting programs, there is a constant c such that a(c+n) >= BB(n).

In particular, a(2+n) >= A333479(n), since for every closed term T, U(00 code(T) : Omega) = (lambda _. T) Omega = T. All entries above except for n=30 are of this form.

We can show that for some k, a(ceiling((113/114)*n) + k) > A333479(n), i.e., universality eventually pays off for BLC. See program link for the supporting computation. - Bertram Felgenhauer, Apr 10 2023