Skip to main content
added 6 characters in body
Source Link
2080
  • 213
  • 1
  • 8

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

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?

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?

Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by 2080
Bounty Started worth 50 reputation by 2080
Source Link
2080
  • 213
  • 1
  • 8

Constraints on the order of program semantics given by an enumeration of turing-complete system programs

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?