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

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.

  • $\begingroup$ I was thinking on the lines that... If the system guarantees a polytime computation bound...for all inputs...isnt it total by definition. $\endgroup$ – ARi Feb 22 '16 at 20:49
  • $\begingroup$ I'd say so. But this only furthers my confusion by cementing what I already believed. $\endgroup$ – Jake Feb 22 '16 at 20:50
  • $\begingroup$ Done. Doing so also helped me think though this a bit but I'm still confused. $\endgroup$ – Jake Feb 22 '16 at 21:09
  • $\begingroup$ You should clarify what you believe and what you (think you) know. Since you've accepted Andrej Bauer's theorem clearly the set of "beliefs" about System B is wrong. Which of them are theorems? $\endgroup$ – Raphael Feb 24 '16 at 9:49
  • $\begingroup$ Everything but the statement "System B can interpret System B" is a theorem. Everything but Andrej's proof from that post is also per-reviewed. So I'm quite convinced that System B can't interpret System B. In fact I would even go so far as to say this constitutes a proof of this fact! My problem is that this seems crazy. I can't think of a counterexample (e.g. a program input pair that can't be evaluated in polynomial time) and I have a strong intuition that System B should be able to interpret System B. But I have no proof of he matter (and indeed I don't think I can have one). $\endgroup$ – Jake Feb 24 '16 at 10:14

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.

  • $\begingroup$ the last sentence is a tautology...? ie essentially by definition? $\endgroup$ – vzn Mar 25 '16 at 20:40
  • $\begingroup$ I fumbled my words, it's fixed now $\endgroup$ – Jake Mar 25 '16 at 20:44

If a language can interpret itself then it is not total

I take this to mean that if there is a universal machine for a class in the class itself, the class can not be total (i.e. there have to be non-total functions in the class). What you probably have in mind is that the class can not be the class of all total computable functions since we know that one to be not recursively enumerable.

However, that does not say anything about any other set of total functions.

For instance, all polynomial-time TMs can be simulated by a single polynomial-time TM. Assuming computable enumerations $M_i$ of all TMs and $p_j$ of the polynomials; both exist. Now consider the following machine UPM (universal polynomial machine):

UPM(<i,j>, n) :
  simulate M_i(n) for p_j(n) steps
  if the computation halts
    return M_i(n)
    return 0

This machine clearly exists (i.e. the described function is computable). Computing $p_j(n)$ and simulating $M_i(n)$ takes only polynomial time (some polynomial effort per simulated step) in $n$ and the size of the $M_i$ (effectively $|\langle i,j \rangle|$), so UPM is a polynomial-time machine itself.

  • $\begingroup$ How does the class of functions that can be computed in polynomial time not contain the function that turing machine encodes? If it does contain that function then the class must not be total right? I must be missing something but I'm just not sure what. $\endgroup$ – Jake Feb 23 '16 at 22:39
  • $\begingroup$ It certainly does contain UPM. Whyever would it not? The claim is that the set of polynomial-time functions/machines contains its own universal machine. Why should that not be possible? Do you have a particular theorem in mind? $\endgroup$ – Raphael Feb 24 '16 at 9:29
  • $\begingroup$ The one Andre presented here which seems quite reasonable to me: cstheory.stackexchange.com/questions/24986/… $\endgroup$ – Jake Feb 24 '16 at 9:39
  • $\begingroup$ @Jake Andrej's setup is different. I don't assume to have a decidable programming language for the set of all polynomial-time function. See also this comment of his. Note that the enumeration works by enforcing the running-time bound by just aborting. $\endgroup$ – Raphael Feb 24 '16 at 9:42
  • 2
    $\begingroup$ FYI, it is possible to define a strongly-typed language which is total and which has a self-interpreter by using the type system to eliminate the diagonalisation argument: compilers.cs.ucla.edu/popl16/popl16-full.pdf $\endgroup$ – Pseudonym Feb 24 '16 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.