2
$\begingroup$

By definition, any formal system (machine, language, etc.) that can compute (simulate) any Turing machine or its equivalent (lambda calculus, recursive functions, etc.) is Turing complete.

I wonder if this property of the system can also be reduced to self-universality, that is, when the system can compute itself. As an example, consider a programming language in which one can create an interpreter program that computes (interprets) any valid string of that very language given on its input.

Would this property automatically make the system Turing complete? Or can one think of a system that is powerful enough to be self-universal but not enough to be Turing complete? Could you provide an example of such a system, please?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Assuming we also have basic arithmetic (which presumably we do, otherwise it is not clear how to represent the syntax of the system within the system), the answer is negative. If there is a self-interpreter then we can compute fixed points (see Theorem 2.2 of this note), but fixed points and natural numbers are sufficient for simulating Turing machines.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! Just to clarify: You mean the answer to the second question, whether a Turing-incomplete self-interpreter exists, is negative. So, the capability of self-interpreting (which must come along with fixed points) is sufficient for Turing-completeness. Did I get you right? $\endgroup$
    – Barney
    Commented Jan 25 at 8:41
  • $\begingroup$ Correct, under technical conditions (namely that you have a reasonable way of representing source code, for instance using coding with natural numbers), if you have a self-interpreter then you have fixed points. $\endgroup$
    – Andrej Bauer
    Commented Jan 25 at 9:31
  • 1
    $\begingroup$ Note that you can fiddle with the definintion of "self-interpreter", and this is what Brown & Palsberg did. The note I linked to explains why their paper, while very nice, is not breaking any barriers. It was POPL propaganda. $\endgroup$
    – Andrej Bauer
    Commented Jan 25 at 9:33

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.