<blockquote>
  <p>Any language which is not Turing complete can not write an interpreter for it self.</p>
</blockquote>

<p>This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore your input and halt immediately".  This programming language is not Turing complete but every program is an interpreter for the language.</p>

CC BY-SA 3.0
2014-06-25T14:37:15.173Z
Ah! That is a good point. So there has to be certain requirements on what the language computes. It seems that some minimum requirement must be made on the power of the language to make that statement true. It seems like if we demand it be able to solve basic arithmetic problems then it might hold.
Jake
CC BY-SA 3.0
2014-06-25T14:51:17.203Z
@Jake You might actually be able to get away with something incredibly weak like "the language defines at least one non-constant function" or "the language defines more than one function". My counterexample is clearly trivial for any reasonable definition of "trivial".
David Richerby
CC BY-SA 3.0
2014-06-25T15:00:03.993Z
Sounds like an interesting problem for me to think about. If I find anything I'll reply back.
Jake
CC BY-SA 3.0
2014-06-24T18:04:40.857Z
2014-06-24T18:04:40.857Z
David Richerby
<p>This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace <span class="math-container">$\mathbb{N}$</span> with <span class="math-container">$\mathtt{string}$</span> throughout below.</p>

<p>Let <span class="math-container">$\langle m, n\rangle$</span> be a <a href="http://en.wikipedia.org/wiki/Pairing_function" rel="noreferrer">pairing function</a>.</p>

<p>Let us say that a programming language <span class="math-container">$L = (P, ev)$</span> is given by the following data:</p>

<ol>
<li>a <em>decidable</em> set <span class="math-container">$P \subseteq \mathbb{N}$</span> of "valid programs", and</li>
<li>a <em>computable</em> and <em>partial</em> function <span class="math-container">$ev : P \times \mathbb{N} \to \mathbb{N}$</span>.</li>
</ol>

<p>The fact that <span class="math-container">$P$</span> is decidable means there is a total computable map <span class="math-container">$valid : \mathbb{N} \to \{0,1\}$</span> such that <span class="math-container">$valid(n) = 1 \iff n \in P$</span>. Informally, we are saying that it is possible to tell whether a given string is a valid piece of code. The function <span class="math-container">$ev$</span> is essentially an interpreter for our language: <span class="math-container">$ev(m,n)$</span> runs code <span class="math-container">$m$</span> on input <span class="math-container">$n$</span> – the result may be undefined.</p>

<p>We can now introduce some terminology:</p>

<ol>
<li>A language is <em>total</em> if <span class="math-container">$n \mapsto ev(m,n)$</span> is a total function for all <span class="math-container">$m \in P$</span>.</li>
<li>A language <span class="math-container">$L_1 = (P_1, ev_1)$</span> <em>interprets</em> language <span class="math-container">$L_2 = (P_2, ev_2)$</span> if there exists <span class="math-container">$u \in P_1$</span> such that <span class="math-container">$ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$</span> for all <span class="math-container">$n \in P_2$</span> and <span class="math-container">$m \in \mathbb{N}$</span>. Here <span class="math-container">$u$</span> is the simulator for <span class="math-container">$L_2$</span> implemented in <span class="math-container">$L_1$</span>. It is also known as the <em>universal program</em> for <span class="math-container">$L_2$</span>.</li>
</ol>

<p>Other definitions of "<span class="math-container">$L_1$</span> interprets <span class="math-container">$L_2$</span>" are possible, but let me not get into this now.</p>

<p>We say that <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span> are equivalent if they interpret each other. </p>

<p>There is "the most powerful" language <span class="math-container">$T = (\mathbb{N}, \varphi)$</span> of Turing machines (which you refer to as "a Turing machine") in which <span class="math-container">$n \in \mathbb{N}$</span> is an encoding of a Turing machine and <span class="math-container">$\varphi(n,m)$</span> is the partial computable function that "runs the Turing machine encoded by <span class="math-container">$n$</span> on input <span class="math-container">$m$</span>". This language can interpret all other languages, obviously since we required <span class="math-container">$ev$</span> to be computable.</p>

<p>Our definition of programming languages is very relaxed. For the following to go through, let us require three more conditions:</p>

<ul>
<li><span class="math-container">$L$</span> implements the successor function: there is <span class="math-container">$succ \in P$</span> such that <span class="math-container">$ev(succ,m) = m+1$</span> for all <span class="math-container">$m \in \mathbb{N}$</span>,</li>
<li><span class="math-container">$L$</span> implements the diagonal function: there is <span class="math-container">$diag \in P$</span> such that <span class="math-container">$ev(diag,m) = \langle m, m \rangle$</span> for all <span class="math-container">$m \in \mathbb{N}$</span>,</li>
<li><span class="math-container">$L$</span> is closed under composition of functions: if <span class="math-container">$L$</span> implements <span class="math-container">$f$</span> and <span class="math-container">$g$</span> then it also implements <span class="math-container">$f \circ g$</span>,</li>
</ul>

<p>A classic result is this:</p>

<p><strong>Theorem:</strong> <em>If a language can interpret itself then it is not total.</em></p>

<p><em>Proof.</em> Suppose <span class="math-container">$u$</span> is the universal program for a total language <span class="math-container">$L$</span> implemented in <span class="math-container">$L$</span>, i.e., for all <span class="math-container">$m \in P$</span> and <span class="math-container">$n \in \mathbb{N}$</span>,
<span class="math-container">$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$</span>
As successor, diagonal, and <span class="math-container">$ev(u, {-})$</span> are implemented in <span class="math-container">$L$</span>, so is their composition <span class="math-container">$k \mapsto ev(u, \langle k, k \rangle) + 1$</span>. There exists <span class="math-container">$n_0 \in P$</span> such that <span class="math-container">$ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$</span>, but then
<span class="math-container">$$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$</span>
As there is no number equal its own successor, it follows that <span class="math-container">$L$</span> is not total or that <span class="math-container">$L$</span> does not interpret itself. QED.</p>

<p>Observe that we could replace the successor map with any other fixpoint-free map.</p>

<p>Here is a little theorem which I think will clean up a misunderstanding.</p>

<p><strong>Theorem:</strong> <em>Every total language can be interpreted by another total language.</em></p>

<p><em>Proof.</em> Let <span class="math-container">$L$</span> be a total language. We get a total <span class="math-container">$L'$</span> which interprets <span class="math-container">$L$</span> by adjoining to <span class="math-container">$L$</span> its evaluator <span class="math-container">$ev$</span>. More precisely, let <span class="math-container">$P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$</span> and define <span class="math-container">$ev'$</span> as
<span class="math-container">$$ev'(\langle b, n \rangle, m) =
\begin{cases}
ev(n,m) &amp; \text{if $b = 0$},\\
ev(m_0, m_1) &amp; \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$}
\end{cases}
$$</span>
Obviously, <span class="math-container">$L'$</span> is total because <span class="math-container">$L$</span> is total. To see that <span class="math-container">$L'$</span> can simulate <span class="math-container">$L$</span> just take <span class="math-container">$u = \langle 1, 0\rangle$</span>, since then
<span class="math-container">$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$</span>, as required. QED.</p>

<p><strong>Exercise:</strong> [added 2014-06-27] The language <span class="math-container">$L'$</span> constructed above is not closed under composition. Fix the proof of the theorem so that <span class="math-container">$L'$</span> satisfies the extra requirements if <span class="math-container">$L$</span> does.</p>

<p>In other words, you <em>never</em> need the full power of Turing machines to interpret a total language <span class="math-container">$L$</span> – a slightly more powerful total language <span class="math-container">$L'$</span> suffices. The language <span class="math-container">$L'$</span> is strictly more powerful than <span class="math-container">$L$</span> because it interprets <span class="math-container">$L$</span>, but <span class="math-container">$L$</span> does not interpret itself.</p>

CC BY-SA 3.0
2014-06-24T10:29:43.193Z
If I checked the wiki checkbox it was unintentional.
Andrej Bauer
CC BY-SA 3.0
2014-06-24T16:05:53.747Z
This is a great answer. You might change the wording of the second theorem to something like "Every total language can be interpreted by another total language that computes strictly more functions than the first."
Joshua Grochow
CC BY-SA 3.0
2014-06-24T19:17:05.267Z
No, that would not be the same theorem. But maybe: every total language may be interpreted by another total language, which therefore computes strictly more functions. In any case, I already said that in the comment after the theorem. I am too lazy to change it.
Andrej Bauer
CC BY-SA 3.0
2014-06-24T19:18:00.357Z
There is a slight problem. The language $L'$ in the second theorem is not closed under composition. This should be fixable, though.
Andrej Bauer
CC BY-SA 3.0
2014-06-25T02:13:31.727Z
Now I'm confused. By your comment after the theorem, doesn't that mean the theorem you wrote and the theorem I wrote are equivalent? I feel like I am missing something obvious here...
Joshua Grochow
CC BY-SA 3.0
2014-06-25T07:51:10.587Z
No, they are not equivalent. You claim there is a strictly more powerful language that simulates a given one. I claim (1) there is a language which simulates the given one and (2) any language that simulates the given one is strictly more powerful than the given one.
Andrej Bauer
CC BY-SA 3.0
2014-06-25T15:21:57.637Z
Ah, I see! Your statement is in fact *stronger* than what I was suggesting. Got it.
Joshua Grochow
CC BY-SA 3.0
2014-06-26T16:37:10.407Z
Is there any extra power in languages where you can't tell whether or not a given program is valid?
Phylliida
CC BY-SA 3.0
2014-06-27T06:55:34.237Z
@DaniPhye: If the language syntax is not semidecidable then you can "hide" computational power in the syntax. For instance, the language rules could require that each function be equipped with a bit which tells whether the function is total. We could then implement `is_total`, which is otherwise non-cmputable, but couldn't implement evaluation (because you'd have to also compute the bit of the resulting function). In general I would say it's not a programming language if you can't even implement a parser for it.
Andrej Bauer
CC BY-SA 3.0
2016-11-17T04:40:47.403Z
How does "If a language can interpret itself then it is not total" gel with this result: [A Self-Interpreter for F-omega](http://compilers.cs.ucla.edu/popl16/)?
Cactus
CC BY-SA 3.0
2016-11-17T07:12:54.860Z
Like this: [A Brown-Palsberg self-interpreter for Gödel’s System T](http://math.andrej.com/2016/01/04/a-brown-palsberg-self-interpreter-for-godels-system-t/)
Andrej Bauer
CC BY-SA 4.0
2014-06-24T08:19:32.067Z
2020-05-18T07:09:33.403Z
2020-05-18T07:09:33.403Z
Andrej Bauer
<p>Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind of "ultimate" non Turing complete language; the one(s) that can <strong>only</strong> be interpreted by a Turing machine. These languages would not necessarily be able to compute all total functions from naturals to naturals nor would they necessarily be isomorphic (that is maybe ultimate languages A and B exists such that there exists a function F that A can compute but B cannot). Agda can interpret Godel's system T and Agda is total so that such an ultimate language should be strictly more powerful that Godel's system T it would seem. It seems to me that such a language would be at least as powerful as agda too (though I have no evidence, just a hunch).</p>

<p>Has any research been done in this vein? What results are known (namely is such an "ultimate" language known)?</p>

<p>Bonus: I am worried that there exists a pathological case that can not compute functions that Godel's System T could yet can still only be interpreted by a Turing machine because it allows some really odd functions to be computed. Is this the case or can we know that such a language would be able to compute anything Godel's System T could compute?</p>

CC BY-SA 3.0
2014-06-23T20:07:12.223Z
Your statements are confusing because of the way you use the terminology. In place of relying on terminology try to state your question in a mathematically rigorous and clear manner so we can understand your question. What do you mean by programming language in the context of computability theory? Do you mean an enumeration of computable functions?
Kaveh
CC BY-SA 3.0
2014-06-23T20:11:17.320Z
My guess about what you read: if a language is strong enough and contains the universal function of another class of functions then it can define the diagonal function for that class. If it is a class of total functions then the diagonal function cannot be in the class.
Kaveh
CC BY-SA 3.0
2014-06-24T01:17:47.287Z
It was stated informally where I found it. Something literally along the lines of what I gave here. I do not know how to state this in a mathematical way either. After some reading I am not sure what the "diagonal function of a class of functions is". I think in your terms what I mean is that "a class of total functions cannot contain its own universal function" and so I think I am asking "for what class of total functions C is it the case that no class of total functions contains the universal function for C". If I understand what a "universal function" is I think that is correct.
Jake
CC BY-SA 3.0
2014-06-24T08:56:55.710Z
Strictly speaking, this is not a research-level question. Also, why is this a community wiki? Or is it?
Andrej Bauer
CC BY-SA 3.0
2014-06-27T15:00:33.703Z
"It seems like this gives rise to a kind of "ultimate" non truing complete language; the one(s) that can only be interpreted by a Turing machine." dont follow that assertion it seems a _non sequitur,_ what do you mean, why does that seem so?
vzn
CC BY-SA 3.0
2014-06-27T15:21:46.287Z
The idea (which we can see is wrong from Andrej's wonderful post) was that there might be a total language which was so powerful (contained so many functions) that only a truing machine (or equivalent) could interpret it.
Jake
<computability><turing-machines>
A total language that only a Turing complete language can interpret
Jake
# A total language that only a Turing complete language can interpret

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

Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind of "ultimate" non Turing complete language; the one(s) that can **only** be interpreted by a Turing machine. These languages would not necessarily be able to compute all total functions from naturals to naturals nor would they necessarily be isomorphic (that is maybe ultimate languages A and B exists such that there exists a function F that A can compute but B cannot). Agda can interpret Godel's system T and Agda is total so that such an ultimate language should be strictly more powerful that Godel's system T it would seem. It seems to me that such a language would be at least as powerful as agda too (though I have no evidence, just a hunch).

Has any research been done in this vein? What results are known (namely is such an "ultimate" language known)?

Bonus: I am worried that there exists a pathological case that can not compute functions that Godel's System T could yet can still only be interpreted by a Turing machine because it allows some really odd functions to be computed. Is this the case or can we know that such a language would be able to compute anything Godel's System T could compute?

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: Your statements are confusing because of the way you use the terminology. In place of relying on terminology try to state your question in a mathematically rigorous and clear manner so we can understand your question. What do you mean by programming language in the context of computability theory? Do you mean an enumeration of computable functions?  
> **username_1**: My guess about what you read: if a language is strong enough and contains the universal function of another class of functions then it can define the diagonal function for that class. If it is a class of total functions then the diagonal function cannot be in the class.  
> **username_0**: It was stated informally where I found it. Something literally along the lines of what I gave here. I do not know how to state this in a mathematical way either. After some reading I am not sure what the "diagonal function of a class of functions is". I think in your terms what I mean is that "a class of total functions cannot contain its own universal function" and so I think I am asking "for what class of total functions C is it the case that no class of total functions contains the universal function for C". If I understand what a "universal function" is I think that is correct.  
> **username_2**: Strictly speaking, this is not a research-level question. Also, why is this a community wiki? Or is it?  
> **username_3**: "It seems like this gives rise to a kind of "ultimate" non truing complete language; the one(s) that can only be interpreted by a Turing machine." dont follow that assertion it seems a _non sequitur,_ what do you mean, why does that seem so?  
> **username_0**: The idea (which we can see is wrong from Andrej's wonderful post) was that there might be a total language which was so powerful (contained so many functions) that only a truing machine (or equivalent) could interpret it.  

---

## 2 answers

### Answer by username_2 on 2014-06-24. Score: 53 | Accepted answer

This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace $\mathbb{N}$ with $\mathtt{string}$ throughout below.

Let $\langle m, n\rangle$ be a [pairing function](http://en.wikipedia.org/wiki/Pairing_function).

Let us say that a programming language $L = (P, ev)$ is given by the following data:

1. a *decidable* set $P \subseteq \mathbb{N}$ of "valid programs", and
2. a *computable* and *partial* function $ev : P \times \mathbb{N} \to \mathbb{N}$.

The fact that $P$ is decidable means there is a total computable map $valid : \mathbb{N} \to \{0,1\}$ such that $valid(n) = 1 \iff n \in P$. Informally, we are saying that it is possible to tell whether a given string is a valid piece of code. The function $ev$ is essentially an interpreter for our language: $ev(m,n)$ runs code $m$ on input $n$ – the result may be undefined.

We can now introduce some terminology:

1. A language is *total* if $n \mapsto ev(m,n)$ is a total function for all $m \in P$.
2. A language $L\_1 = (P\_1, ev\_1)$ *interprets* language $L\_2 = (P\_2, ev\_2)$ if there exists $u \in P\_1$ such that $ev\_1(u, \langle n, m \rangle) \simeq ev\_2(n, m)$ for all $n \in P\_2$ and $m \in \mathbb{N}$. Here $u$ is the simulator for $L\_2$ implemented in $L\_1$. It is also known as the *universal program* for $L\_2$.

Other definitions of "$L\_1$ interprets $L\_2$" are possible, but let me not get into this now.

We say that $L\_1$ and $L\_2$ are equivalent if they interpret each other.

There is "the most powerful" language $T = (\mathbb{N}, \varphi)$ of Turing machines (which you refer to as "a Turing machine") in which $n \in \mathbb{N}$ is an encoding of a Turing machine and $\varphi(n,m)$ is the partial computable function that "runs the Turing machine encoded by $n$ on input $m$". This language can interpret all other languages, obviously since we required $ev$ to be computable.

Our definition of programming languages is very relaxed. For the following to go through, let us require three more conditions:

* $L$ implements the successor function: there is $succ \in P$ such that $ev(succ,m) = m+1$ for all $m \in \mathbb{N}$,
* $L$ implements the diagonal function: there is $diag \in P$ such that $ev(diag,m) = \langle m, m \rangle$ for all $m \in \mathbb{N}$,
* $L$ is closed under composition of functions: if $L$ implements $f$ and $g$ then it also implements $f \circ g$,

A classic result is this:

**Theorem:** *If a language can interpret itself then it is not total.*

*Proof.* Suppose $u$ is the universal program for a total language $L$ implemented in $L$, i.e., for all $m \in P$ and $n \in \mathbb{N}$,
$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$
As successor, diagonal, and $ev(u, {-})$ are implemented in $L$, so is their composition $k \mapsto ev(u, \langle k, k \rangle) + 1$. There exists $n\_0 \in P$ such that $ev(n\_0, k) \simeq ev(u, \langle k, k \rangle) + 1$, but then
$$ev(u, \langle n\_0, n\_0\rangle) \simeq ev(n\_0, n\_0) \simeq ev(u, \langle n\_0, n\_0 \rangle) + 1$$
As there is no number equal its own successor, it follows that $L$ is not total or that $L$ does not interpret itself. QED.

Observe that we could replace the successor map with any other fixpoint-free map.

Here is a little theorem which I think will clean up a misunderstanding.

**Theorem:** *Every total language can be interpreted by another total language.*

*Proof.* Let $L$ be a total language. We get a total $L'$ which interprets $L$ by adjoining to $L$ its evaluator $ev$. More precisely, let $P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$ and define $ev'$ as
$$ev'(\langle b, n \rangle, m) =
\begin{cases}
ev(n,m) & \text{if $b = 0$},\\
ev(m\_0, m\_1) & \text{if $b = 1$ and $m = \langle m\_0, m\_1 \rangle$}
\end{cases}
$$
Obviously, $L'$ is total because $L$ is total. To see that $L'$ can simulate $L$ just take $u = \langle 1, 0\rangle$, since then
$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$, as required. QED.

**Exercise:** [added 2014-06-27] The language $L'$ constructed above is not closed under composition. Fix the proof of the theorem so that $L'$ satisfies the extra requirements if $L$ does.

In other words, you *never* need the full power of Turing machines to interpret a total language $L$ – a slightly more powerful total language $L'$ suffices. The language $L'$ is strictly more powerful than $L$ because it interprets $L$, but $L$ does not interpret itself.

> **Comments:**
> **username_2**: If I checked the wiki checkbox it was unintentional.  
> **username_5**: This is a great answer. You might change the wording of the second theorem to something like "Every total language can be interpreted by another total language that computes strictly more functions than the first."  
> **username_2**: No, that would not be the same theorem. But maybe: every total language may be interpreted by another total language, which therefore computes strictly more functions. In any case, I already said that in the comment after the theorem. I am too lazy to change it.  
> **username_2**: There is a slight problem. The language $L'$ in the second theorem is not closed under composition. This should be fixable, though.  
> **username_5**: Now I'm confused. By your comment after the theorem, doesn't that mean the theorem you wrote and the theorem I wrote are equivalent? I feel like I am missing something obvious here...  
> **username_2**: No, they are not equivalent. You claim there is a strictly more powerful language that simulates a given one. I claim (1) there is a language which simulates the given one and (2) any language that simulates the given one is strictly more powerful than the given one.  
> **username_5**: Ah, I see! Your statement is in fact *stronger* than what I was suggesting. Got it.  
> **username_6**: Is there any extra power in languages where you can't tell whether or not a given program is valid?  
> **username_2**: @DaniPhye: If the language syntax is not semidecidable then you can "hide" computational power in the syntax. For instance, the language rules could require that each function be equipped with a bit which tells whether the function is total. We could then implement `is_total`, which is otherwise non-cmputable, but couldn't implement evaluation (because you'd have to also compute the bit of the resulting function). In general I would say it's not a programming language if you can't even implement a parser for it.  
> **username_7**: How does "If a language can interpret itself then it is not total" gel with this result: [A Self-Interpreter for F-omega](http://compilers.cs.ucla.edu/popl16/)?  
> **username_2**: Like this: [A Brown-Palsberg self-interpreter for Gödel’s System T](http://math.andrej.com/2016/01/04/a-brown-palsberg-self-interpreter-for-godels-system-t/)  

---

### Answer by username_4 on 2014-06-24. Score: 22

> Any language which is not Turing complete can not write an interpreter for it self.

This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore your input and halt immediately". This programming language is not Turing complete but every program is an interpreter for the language.

> **Comments:**
> **username_0**: Ah! That is a good point. So there has to be certain requirements on what the language computes. It seems that some minimum requirement must be made on the power of the language to make that statement true. It seems like if we demand it be able to solve basic arithmetic problems then it might hold.  
> **username_4**: @Jake You might actually be able to get away with something incredibly weak like "the language defines at least one non-constant function" or "the language defines more than one function". My counterexample is clearly trivial for any reasonable definition of "trivial".  
> **username_0**: Sounds like an interesting problem for me to think about. If I find anything I'll reply back.  

---

