<p>This hardly says anything about the poset structure, but this <a href="https://www.sciencedirect.com/science/article/pii/0304397580900171" rel="nofollow noreferrer">paper</a> of Dexter Kozen shows that the diagonal function of certain indexings of PTIME obtained from clocked Turing machines is not contained in PSPACE. An &quot;indexing of PTIME&quot; 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.</p>

CC BY-SA 4.0
2022-12-11T16:17:59.490Z
2022-12-11T16:17:59.490Z
Siddharth
<p>Inspired by <a href="https://cstheory.stackexchange.com/a/24994/129">this answer</a>, let's say that a <em>programming language</em> 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^*$). </p>

<p>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).</p>

<blockquote>
  <p><em>Definition:</em>  $L_1=(P_1, ev_1)$ <em>interprets</em> $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$. </p>
  
  <p><em>Definition</em>: $L_1$ and $L_2$ have the same "interpretability degree" if each interprets the other. </p>
  
  <p><em>Definition:</em> $(P,ev)$ is <em>total</em> if for all $p \in P$, the function $x \mapsto ev(p,x)$ is total.</p>
</blockquote>

<p>My question is:</p>

<blockquote>
  <p><strong>Question:</strong> What is known about the poset of interpretability degrees? </p>
  
  <p>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.</p>
  
  <p>I'd also be interested in the same questions but where we now require the interpreters to be <em>efficient</em> - that is, to preserve the Turing-machine time and space complexity up to polynomial factors.</p>
</blockquote>

<p>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.)</p>

<p><strong>Answers I already know:</strong> 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). <a href="https://cstheory.stackexchange.com/a/24994/129">Andrej Bauer's answer</a> 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.</p>

CC BY-SA 3.0
2014-06-27T08:38:35.670Z
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.
Kaveh
CC BY-SA 3.0
2014-06-27T13:06:15.797Z
@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).
Joshua Grochow
CC BY-SA 3.0
2014-06-29T16:29:17.873Z
I'd look at John Longley's theory of applicative morphisms.
Andrej Bauer
CC BY-SA 3.0
2014-06-29T16:30:05.127Z
Also, I think my definition of "inteprets" is ad hoc and not very good.
Andrej Bauer
CC BY-SA 3.0
2014-06-29T19:14:19.637Z
@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...
Joshua Grochow
CC BY-SA 3.0
2014-06-29T19:25:06.033Z
For starters, $P$ should be a computable enumerable set, not computable one. I am also highly tempted to state that all primitive recursive functions should be implemented, so the lowest level should be the primitive recursive functions. If not, then at least we should include conditional statements.
Andrej Bauer
CC BY-SA 3.0
2014-06-29T19:35:23.360Z
@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...
Joshua Grochow
<cc.complexity-theory><reference-request><pl.programming-languages><computability><reductions>
What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?
Joshua Grochow
# What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?

(Asked by: username_0 on 2014-06-25)

Inspired by [this answer](https://cstheory.stackexchange.com/a/24994/129), 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). [username_2's answer](https://cstheory.stackexchange.com/a/24994/129) 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.

**Tags:** cc.complexity-theory, reference-request, pl.programming-languages, computability, reductions

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: 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).  
> **username_2**: I'd look at John Longley's theory of applicative morphisms.  
> **username_2**: Also, I think my definition of "inteprets" is ad hoc and not very good.  
> **username_0**: @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...  
> **username_2**: For starters, $P$ should be a computable enumerable set, not computable one. I am also highly tempted to state that all primitive recursive functions should be implemented, so the lowest level should be the primitive recursive functions. If not, then at least we should include conditional statements.  
> **username_0**: @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...  

---

## 1 answers

### Answer by username_3 on 2022-12-11. Score: 1

This hardly says anything about the poset structure, but this [paper](https://www.sciencedirect.com/science/article/pii/0304397580900171) 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.


---

