21

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?

Linas
  • 103
  • 4
Jake
  • 1,203
  • 7
  • 20
  • 2
    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 Jun 23 '14 at 20:07
  • 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. – Kaveh Jun 23 '14 at 20:11
  • 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 Jun 24 '14 at 01:17
  • 1
    Strictly speaking, this is not a research-level question. Also, why is this a community wiki? Or is it? – Andrej Bauer Jun 24 '14 at 08:56
  • "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 Jun 27 '14 at 15:00
  • 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 Jun 27 '14 at 15:21

2 Answers2

51

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.

Couchy
  • 195
  • 5
Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
  • If I checked the wiki checkbox it was unintentional. – Andrej Bauer Jun 24 '14 at 10:29
  • 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 Jun 24 '14 at 16:05
  • 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 Jun 24 '14 at 19:17
  • There is a slight problem. The language $L'$ in the second theorem is not closed under composition. This should be fixable, though. – Andrej Bauer Jun 24 '14 at 19:18
  • 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 Jun 25 '14 at 02:13
  • 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 Jun 25 '14 at 07:51
  • Ah, I see! Your statement is in fact stronger than what I was suggesting. Got it. – Joshua Grochow Jun 25 '14 at 15:21
  • 3
    Is there any extra power in languages where you can't tell whether or not a given program is valid? – Phylliida Jun 26 '14 at 16:37
  • 6
    @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 Jun 27 '14 at 06:55
  • 5
    How does "If a language can interpret itself then it is not total" gel with this result: A Self-Interpreter for F-omega? – Cactus Nov 17 '16 at 04:40
  • 5
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.

David Richerby
  • 2,765
  • 2
  • 18
  • 28
  • 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 Jun 25 '14 at 14:37
  • @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 Jun 25 '14 at 14:51
  • Sounds like an interesting problem for me to think about. If I find anything I'll reply back. – Jake Jun 25 '14 at 15:00