| Good question. BB is certainly an upper bound. Consider the problem P_f of getting an input x and having to compute a value >= f(x), where both the input and the output are encoded in unary. We know that BB grows faster than any computable function, so P_BB cannot be computable. Suppose for contradiction that there was a computable problem Q with time complexity Omega(BB(x)). This means there exists a Turing Machine M that computes Q and a function T(n), such that for each n there exists an input y of length n, such that M halts after exactly T(n) steps. Moreover, T(n) = Omega(BB(x)). Then we can construct a Turing Machine M' that computes P_BB. The idea is to run a TM for Q on a length x input and counting the number of computation steps. That number is then larger than BB(n) and thus a valid output for P_BB. Formally: Let M be a TM that computes Q. Without loss of generality we assume that M uses a binary tape alphabet. Since T(n) = Omega(BB(x)), there exists per definition a C > 0 and an k_0 > 0 such that for all k > k_0 it holds that C*BB(k) <= T(k). M' now operates as follows. Given a unary input x, M' first checks if |x| <= k_0. If yes, M' just outputs BB(|x|). Otherwise, M' enumerates all bitstrings y of length |x|. For each y, M' then runs Q on y step-by-step while incrementing a unary counter c_y. Finally, M' outputs the longest such c_y, divided by C. Per assumption, the longest c_y satisfies C*BB(|x|) <= c_y, so c_y/C >= BB(|x|). This implies that P_BB is computable, contradicting our initial observation. Consequently, such a Q cannot exist. In fact, this proof works for any function that grows faster than all computable functions. This means that BB as an upper bound is not tight. For example log(BB) also satisfies this property. |