This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael Stay's paper Very Simple Chaitin Machines for Concrete AIT [algorithmic information theory].
A Chaitin machine is a partial recursive function whose inputs and outputs (when defined) are finite binary strings, such that the viable input strings - which can be thought of as "programs", and need not give an output - form a prefix-free code. In other words, if $s$ and $st$ are viable programs, where $st$ denotes the concatenation of $s$ and $t$, then $t$ is the null string. For more detailed discussion see Stay's paper linked above. The set of Chaitin machines is obviously countable; let $m_i$ denote the $i$th machine according to some indexing (the details should be unimportant), and $m_i(s)$ the result of running program $s$ on machine $m_i$.
A Chaitin machine $m_i$ is said to be universal if for every Chaitin machine $m_j$ there is a program $int_{i,j}$ such that $m_i(int_{i,j}s) = m_j(s)$ for every program $s$. $int_{i,j}$ is called an interpreter for $m_j$ in $m_i$. Universal Chaitin machines are known to exist, but note that being universal as a Chaitin machine is stronger than being a Chaitin machine which is Turing-complete: $m_i$ must be able to interpret every $m_j$ with constant overhead.
Let $C_i(s)$ denote the Kolmogorov complexity of the string $s$ in the machine $m_i$: that is, the length in bits of the shortest program in $m_i$ which outputs $s$. If $m_i$ is universal then the dependence of $C_i(s)$ on $m_i$ is effectively an additive constant independent of $s$: that is, if $I_{i,j}$ is the length of a shortest interpreter for $m_j$ in $m_i$ then $C_i(s) \le I_{i,j} + C_j(s)$.
I am interested in the behaviour of $I_{i,j}$ as a function of (especially) $j$. My intuition is this: in any given $m_i$ which is universal, it is certainly possible to devise an artificially long program which behaves as an interpreter for some $m_j$; and it's conceivable to me that there could be a "pseudo-uniform" way to come up with some particular $m_j$ (dependent on $m_i$) such that all interpreters for $m_j$ in $m_i$ must be long, i.e. $I_{i,j}$ must be large. Is it then true that some $m_j$ will "usually" need a longer interpreter in the various $m_i$ than will another $m_{j_0}$? In other words, are some universal Chaitin machines inherently "more complex" than others? Or if not, is there at least a way to describe some of the local and global properties of the "asymmetric distance" function $I$?
My feeling is that there should be some meaningful "absolute" sense in which machines such as those in Stay's paper can be considered simple, but this might be hard to pin down...
(Wasn't quite sure how to tag this one; feel free to change some of the tags.)
There was originally an extra question, which I'd still be interested in addressing if it can be made precise:
Consider the class of Turing-equivalent models of computation whose programs and data are encoded as finite binary strings. Any such model lives in a countable equivalence class of models which have (finite) interpreters for each other; we can restrict ourselves to considering the countable class containing some familiar model.
(As an aside, I'm not sure how or if one could explicitly describe a model not belonging to this familiar class. Could there be some sort of diagonalization argument which allows one to ensure Turing-equivalence of the result? Or are there really only countably many such models in the first place...? Maybe this deserves its own question, but I suspect the answer's completely trivial once the right concepts are formulated.)
