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.