There are Turing-complete systems like Jot where every natural number represents a valid program. This results in a Gödel numbering.

Now, if the semantics of the programs were, say

| N | Semantics |
| 0 | input + 0 |
| 1 | input + 1 |
| 2 | input + 2 |
| 3 | input + 3 |

etc., then the numbering would never reach other kinds of semantics, like multiplication ("input * 0", "input * 1", "input * 2" etc.) and all other possible computable functions.

So, since this seems like a contradiction of the fact that the system is Turing-complete, does that mean that the program number <-> semantics mapping sequence must follow a different pattern that eventually reaches every possible semantics, without having any one pattern going into infinity?

In other words, does a system being Turing-complete set constraints on the (order of) program semantics enumerated by a Gödel numbering? If so, can anything more detailed said about them?


1 Answer 1


A Tuing-complete programming language has the property that there is a surjection $c : \mathbb{N} \to \mathsf{Prog}$ (the set of all valid programs in whatever model of computation you have). We call $n$ the Gödel code of the program $c(n)$.

Several important theorems rely on having such a map $c$, for example the proof that there exists a universal Turng machine. In fact, in those theorems $c$ must not only be surjective, but also acceptable. This is a technical condition, and I think it is the one you are asking for (in addition to $c$ being surjective). A computable map $c : \mathbb{N} \to \mathsf{Prog}$ is acceptable, if it can be used to show that $\mathsf{Prog}$ is Turing-complete, i.e., there is a Turing machine $T$ (the interpreter) such that $T(n)$ "does the same thing" as $c(n)$. Inutitively, this says that a Turing machine can actually figure out what $n$ encodes. Please look up the exact condition in a book on computability.

There are of course other maps $\mathbb{N} \to \mathsf{Prog}$, and if you replace an acceptable surjection $c$ with one of them, you will break the proofs of those theorems.


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.