I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter.

What's wrong with the following argument:

If there's an interpreter int let's define the program p:

read x;
int(x,y) //I just copy the code of int that ends with:
write output; 

Now if we run p on p we get an infinite loop.


  1. I assume the language is non recursive but has assignments and conditional statements, creating pair and accessing their coordinates. Programs are lists that can read as inputs. Something like Scheme. (If any of these assumptions can be relaxed it's interesting too.)

  2. I know how to prove the theorem. I wonder about this (suspicious) proof.


Interesting. Let's formalize your argument.

Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, \ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I \ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)

Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$

Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.

However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.

  • $\begingroup$ Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed. $\endgroup$
    – OMGsh
    Jan 14 '19 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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