Implicit complexity and interpretation of total languages

In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be characterized by such a language (called system $B$).

I have the following beliefs about system $B$

• System B can encode all functions which can be computed in polynomial time

• All terms in System $B$ normalize in polynomial time

• Because all System $B$ terms normalize (in any amount of time) System $B$ is total

• Because all System $B$ terms normalize in polynomial time System $B$ can interpret System $B$

I have the following beliefs a computability as well

• If a language can interpret itself then it is not total

• System $B$ can interpret it self so System $B$ is not total

So I seem to believe contradictory things now; namely that System $B$ is total and that System $B$ is not total. Writing out like this makes me realize that the error is almost certainly in the last line of my beliefs about System $B$. So it must be the case that System $B$ can't interpret itself but I don't actually understand why this is the case. Is there a program input pair such that interpreting it takes greater than polynomial time? Further still System $B$ is just one such system among all characterizations of complexity classes on which I could apply this faulty reasoning so the answer should not be specific to System $B$ but to all such implicit characterizations of complexity classes.

As concluded via non-direct means in discussion interpreting a polytime program cannot be done in polynomial time in general. The following example shows this directly.

The trick is that for the interpreter to run in polynomial time there must be an polynomial that bounds the running time for every input. This pretty obviously isn't going to hold for System-$B$ because a small constant increase in program size can increase the order of the polynomial that bounds it by a constant amount. The trick you can fall into (and I indeed fell into) is to think that because for each program the running time is bounded a polynomial that the interpreter will run in polynomial time which is pretty embarrassingly obviously false when you write it out like this. It's running time on certain inputs will be bounded by some polynomial but that's the case for any program that always terminates.

So say there is a program, $I$ in System-$B$ that interprets System-$B$ and has running time in $O(n^k)$. Say I had another program, $P$, that ran in $O(n^K)$ with $K > k$. We could speed up P to $O(n^k)$ by simply running it though the interpreter first. So suddenly you have a huge speed up on $P$ that you shouldn't be able to get. In general $I$ could speed up any program slower than it.

I don't have a proof there is no $k$ such that every polytime function can be computed in $O(n^k)$ but it seems fairly obviously the case.

StackExchange Computer Science Q#53485, answer score: 2