Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") is a partial computable function $ev:P \times \Sigma^* \to \Sigma^*$, where $\Sigma$ is a finite alphabet. Let's also require that a programming language contains the successor functions $x \mapsto xa$ for each $a \in \Sigma$, the diagonal function $x \mapsto \langle x, x \rangle$, and is closed under composition. (As usual, $\langle a, b \rangle$ is a computable and computably-invertible-in-both-arguments pairing function $\Sigma^* \times \Sigma^* \to \Sigma^*$).

If you want to add some other natural/obvious ones (e.g. the projections $\pi_i(\langle x_1, x_2 \rangle) = x_i$) that should be okay, but nothing too powerful (e.g. don't require that every programming language has a universal interpreter).

Definition: $L_1=(P_1, ev_1)$ interprets $L_2=(P_2, ev_2)$ if there is a program $p_{12} \in P_1$ that is universal for $L_2$, i.e. $ev_1(p_{12}, \langle p, x \rangle) \simeq ev_2(p, x)$ for all $p,x$.

Definition: $L_1$ and $L_2$ have the same "interpretability degree" if each interprets the other.

Definition: $(P,ev)$ is total if for all $p \in P$, the function $x \mapsto ev(p,x)$ is total.

My question is:

Question: What is known about the poset of interpretability degrees?

For example, is it a lattice (probably not)? Are there minimal degrees strictly above the bottom? Are there maximal degrees strictly below Turing-universal? Is every finite/countable/blah poset a sub-poset of this one? Is there a non-Turing-universal (and, necessarily, non-total) least upper bound on the total languages? etc.

I'd also be interested in the same questions but where we now require the interpreters to be efficient - that is, to preserve the Turing-machine time and space complexity up to polynomial factors.

Results, references, and keywords are all appreciated. (If there end up being lots of answer this may become a community wiki, but I don't anticipate that.)

Answers I already know: Turing-universal is the unique top element of this poset. The smallest set of functions containing successor, diagonal, and closed under composition is the unique bottom element (one can easily cook up a programming language according to the above definition which only computes such functions). Andrej Bauer's answer to another question shows that no total language interprets all total languages, and further that there are strictly increasing infinite chains, even amongst the total languages.

  • 1
    $\begingroup$ I guess it is quite similar to the poset of r.e. degrees. Do we have any property that distinguishes them? ps: the requirements reminds me of Kozen's definition of complexity class in his indexing of subrecursive functions paper. $\endgroup$
    – Kaveh
    Jun 27, 2014 at 8:38
  • 2
    $\begingroup$ @Kaveh: That was my guess as well (hence my example questions), but there are already some differences. For example, the poset in my question has lots of total computable programming languages, whereas in the poset of c.e. degrees, "computable" is just a single point (the bottom). $\endgroup$ Jun 27, 2014 at 13:06
  • $\begingroup$ I'd look at John Longley's theory of applicative morphisms. $\endgroup$ Jun 29, 2014 at 16:29
  • $\begingroup$ Also, I think my definition of "inteprets" is ad hoc and not very good. $\endgroup$ Jun 29, 2014 at 16:30
  • 1
    $\begingroup$ @AndrejBauer: Including all primitive recursive functions seems like a reasonable thing to do, since it basically amounts to including conditionals and simple loops. Even with that modification, the question still seems quite interesting to me, and it still differs from the c.e. degrees for the same reason as above. Why would you want the set of valid programs to be c.e.? I found your comment on that other questions a pretty convincing reason that $P$ should be computable... $\endgroup$ Jun 29, 2014 at 19:35

1 Answer 1


This hardly says anything about the poset structure, but this paper of Dexter Kozen shows that the diagonal function of certain indexings of PTIME obtained from clocked Turing machines is not contained in PSPACE. An "indexing of PTIME" is simply a kind of programming language (at the level of generality presented in the question), and if a programming language interprets another, it certainly computes its diagonal function.


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.