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 '14 at 8:38
  • 1
    $\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$ – Joshua Grochow Jun 27 '14 at 13:06
  • $\begingroup$ I'd look at John Longley's theory of applicative morphisms. $\endgroup$ – Andrej Bauer Jun 29 '14 at 16:29
  • $\begingroup$ Also, I think my definition of "inteprets" is ad hoc and not very good. $\endgroup$ – Andrej Bauer Jun 29 '14 at 16:30
  • $\begingroup$ @AndrejBauer: Even if it was ad hoc, why do you think it's not very good? Also, not very good from what perspective? Programming Languages? Because to me, it seems quite good from a computability-theoretic (and perhaps even complexity-theoretic) point of view... $\endgroup$ – Joshua Grochow Jun 29 '14 at 19:14

Your Answer

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

Browse other questions tagged or ask your own question.