<p>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 <a href="https://math.andrej.com/wp-content/uploads/2016/01/self-interpreter-for-T.pdf" rel="nofollow noreferrer">this note</a>), but fixed points and natural numbers are sufficient for simulating Turing machines.</p>

CC BY-SA 4.0
2024-01-25T08:41:14.070Z
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?
Barney
CC BY-SA 4.0
2024-01-25T09:31:45.647Z
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.
Andrej Bauer
CC BY-SA 4.0
2024-01-25T09:33:13.873Z
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.
Andrej Bauer
CC BY-SA 4.0
2024-01-25T08:32:36.003Z
2024-01-25T08:32:36.003Z
Andrej Bauer
<p>By definition, any formal system (machine, language, etc.) that can compute (simulate) any Turing machine or its equivalent (lambda calculus, recursive functions, etc.) is <strong>Turing complete</strong>.</p>
<p>I wonder if this property of the system can also be reduced to <em>self-universality</em>, 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.</p>
<p>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?</p>

<turing-machines><universal-computation><universal-turing-machines>
Self-universality and Turing-completeness
Barney
# Self-universality and Turing-completeness

(Asked by: username_0 on 2024-01-25)

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?

**Tags:** turing-machines, universal-computation, universal-turing-machines

---

## 1 answers

### Answer by username_1 on 2024-01-25. Score: 3 | Accepted answer

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](https://math.andrej.com/wp-content/uploads/2016/01/self-interpreter-for-T.pdf)), but fixed points and natural numbers are sufficient for simulating Turing machines.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: 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.  

---

