Can we find a computable function which cannot be calculated faster for any given time?

Question

Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by:

$T(k,n) = 2^{T(k-1,n)}$

$T(0,n) = 1$

$T(1,n) = 2^n$

$T(2,n) = 2^{2^n}$

And denote the W.C. (worst case) time of computing $f(n)$ as $WC(f(n))$

Can we find computable functions $f_i\colon \mathbb{N} \rightarrow \mathbb{N}$ such that computing $f_i(n)$ takes $\Omega(T(i,n))$ W.C. and such that for every other computable function $f \equiv f_i$ (I mean $f(n) = f_i(n) \forall n \in \mathbb{N}$), we have $\lim_{n \rightarrow \infty} \frac{WC(f_i(n))}{WC(f(n))} \neq 0$?

I am in a sense trying to find a concrete example of functions that takes at least X time to compute, where X can be as large (asymptotically) as we want.

I was thinking maybe $f_i(n) =$ the $T(i,n)$'th digit of $\pi$, but not quite sure this fulfills the second condition.

Answer 1

The "$f$-bounded halting problem" takes time at least (roughly) $f$ (for infinitely many $n$). The $f$-bounded halting problem asks whether a Turing machine halts on the input $0^n$ within time $f(n)$. Suppose we could solve this problem in time $g(n)$. Consider the following machine:

On input $0^n$, ask whether the $n$th Turing machine halts within time $f(n)$ on the input $0^n$. If so, go into an infinite loop, and otherwise, halt.

This takes time $g(n) + Cn$ for some constant $C$. If $g(n) + Cn \leq f(n)$ then we obtain a contradiction by taking $n$ to be the code of this machine. Hence the $f$-bounded halting problem cannot be solved in time $f(n) - Cn$.

This argument only shows that we need time $f(n) - Cn$ for some $n$. But we could consider an infinite sequence of Turing machines equivalent to the one described above, and so obtain an "infinitely often" version of this statement.

It is possible that through trickery we can improve this to all $n$ (for reasonable functions $f$), and leave this for the reader to ponder.