Eigenratio

The eigenratio of a self-interpreter (i.e. an interpreter written in the same language that it interprets) is a measure in the limit of the slowdown when several copies (a stack) of it are chained, each interpreting the next and the last one interpreting some arbitrary "outermost" program. The concept was named and investigated by Clive Gifford.

The name is based on "eigenvalue", as at least in simple cases it can be calculated as the largest eigenvalue of an explicitly constructed matrix with entries that are the number of each type of instruction needed to be run by an "inner" interpreter to simulate a given type of instruction in an "outer" one.

Definition

Given a self-interpreter $I$ and an outermost terminating program $P$, let $f(n,I,P)$ be the number of instructions run by the innermost interpreter in a stack of $n$ of them where the outermost is interpreting $P$.

If the limit

$$\lim _{n\rightarrow \infty }{\frac {f(n+1,I,P)}{f(n,I,P)}}.$$

exists for all terminating $P$ and is independent of $P$, then we call it the eigenratio of $I$.

More generally, the limit may not always exist, and may not always be independent of $P$. One case where the eigenratio does exist is if the self-interpreter is described by a primitive matrix.

External resources

• Eigenratios of Self Interpreters