21
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$
    – Kaveh
    Commented Jun 23, 2014 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jun 23, 2014 at 20:11
  • $\begingroup$ 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. $\endgroup$
    – Jake
    Commented Jun 24, 2014 at 1:17
  • 1
    $\begingroup$ Strictly speaking, this is not a research-level question. Also, why is this a community wiki? Or is it? $\endgroup$ Commented Jun 24, 2014 at 8:56
  • $\begingroup$ "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? $\endgroup$
    – vzn
    Commented Jun 27, 2014 at 15:00

2 Answers 2

53
$\begingroup$

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.

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.

$\endgroup$
11
  • $\begingroup$ If I checked the wiki checkbox it was unintentional. $\endgroup$ Commented Jun 24, 2014 at 10:29
  • 3
    $\begingroup$ Is there any extra power in languages where you can't tell whether or not a given program is valid? $\endgroup$
    – Phylliida
    Commented Jun 26, 2014 at 16:37
  • 6
    $\begingroup$ @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. $\endgroup$ Commented Jun 27, 2014 at 6:55
  • 5
    $\begingroup$ How does "If a language can interpret itself then it is not total" gel with this result: A Self-Interpreter for F-omega? $\endgroup$
    – Cactus
    Commented Nov 17, 2016 at 4:40
  • 5
    $\begingroup$ Like this: A Brown-Palsberg self-interpreter for Gödel’s System T $\endgroup$ Commented Nov 17, 2016 at 7:12
22
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Jake
    Commented Jun 25, 2014 at 14:37
  • $\begingroup$ @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". $\endgroup$ Commented Jun 25, 2014 at 14:51
  • $\begingroup$ Sounds like an interesting problem for me to think about. If I find anything I'll reply back. $\endgroup$
    – Jake
    Commented Jun 25, 2014 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.