1
$\begingroup$

There are Turing-complete systems like Jot where every natural number can be mapped to 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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This isn't an answer, but one important fact about these orderings would be Kleene's recursion theorem. $\endgroup$ Commented Jun 17, 2024 at 22:08

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Apparently this is also called en.wikipedia.org/wiki/Admissible_numbering $\endgroup$ Commented Apr 6 at 6:41
  • $\begingroup$ Yeah, the terminology isn't exactly fixed. $\endgroup$ Commented Apr 6 at 16:37

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.