Recently I had to prove some theorems about programming languages. Originally I thought that I could assume that for every programming language there is a compiler that compiles that language into every other programming language and vice versa. Apparently this is wrong and I only have a partial proof of why this is so. So I was wondering if anyone has heard anything about this problem. The exact formalisation is as follows:
Let $ P $ be the set of all computable functions.
A programming language is a computable function $ \psi $ in two arguments $ e, x $, where $ e $ is the Gödel number and $ x $ is the input. For $ \psi $, it must hold that for all $ f \in P $, there exists $ e \in \mathbb{N} $ such that $ \forall x: \psi(e, x) = f(x) $. We also define $ \psi_e := x \mapsto \psi(e, x) $. In other words, a computable function is a programming language if and only if every computable function in this programming language has a program.
We define an order $ \leq_R $ on programming languages as follows. For all programming languages $ \psi, \theta $, let
$$ \psi \leq_R \theta \Leftrightarrow \exists t \in P \forall e \in \mathbb{N} : \psi_e = \theta_{t(e)} $$
To prove: Let $\psi, \theta$ be programming languages. It follows that $\psi \leq_R \theta$