Definition talk:Code Number for Integer

The purpose of this page is not to prove the integers countably infinite, but to establish a single canonical coding scheme for all work on recursive functions. Still, I'm not aware of this other thread, and I'd like to take a look at it. Could you point me to it? --CircuitCraft (talk) 14:08, 9 September 2023 (UTC)

It doesn't matter what it's for, it's the fact that "integer coding" is a lame name.

Point is, there are many possible ways of coding an integer. If anything, "integer coding" should be a definition of what an integer coding actually is. Then the various examples of what integer codings there are, and for what specific use each one is (although there is only ultimately one reason for using one) can be included, along with (as appropriate) what you can't use this integer coding for. --prime mover (talk) 22:21, 9 September 2023 (UTC)

Incidentally, have we even defined "coding"? --prime mover (talk) 23:14, 9 September 2023 (UTC)

The thread I was talking about can be found along with the unsourced stuff around URM computability, and so on. The use of the term "integer coding" is usually completely different to how you are defining it.

For a start, it comes across as a bit pompous call it a "coding". It's just a bijection. And you would go: "Let us define the bijection $\forall x \in \Z: \map f x = \begin {cases} 2 x - 1 & : x > 0 \\ -2 x & : n \le 0 \end {cases}$." (That is how it would be rigorously defined, and yes, we may indeed want to reference it when we want to demonstrate the equivalence of $\N$ and $\Z$, which is usually done during undergraduate preparations.)

It is also a perfect metaphor for the art and science of spinning a length of wool from a scrap of fleece. --prime mover (talk) 23:17, 9 September 2023 (UTC)

We are not going to waste the concept of "integer coding" (still to be done, sorry, we really should be getting on with putting the basic vocabulary for that in place as well, another job to do) on such a simple (some would rhetorise and call it "trivial") bijection whose main job is to prove equivalence of $\N$ and $\Z$.

As for "establish a canonical coding scheme for all work on recursive functions", well maybe, but while it looks simple, I'm pretty sure that what you're looking for ain't this. And if it is only a stepping-stone along the way, do what you want but please do not call this an "integer coding" because it ain't one of them.

The concept of using a code number to encode something of importance into an integer is a lot wider than just a simple matter of this bijection between $\Z$ and $\N$.

An example would be by encoding a statement in Godel theory into a unique number which consists of creating the number which is the product of the $n$th prime to the power of the integer interpretation of the $n$th character, but it was long ago and I the details have not stayed with me. Never put a trace through it, come to think off it. Not sure if I actually got that far. --prime mover (talk) 23:14, 9 September 2023 (UTC)

Ah, I guess the name could be misinterpreted that way. By "integer coding," I meant that the thing we are coding is an integer, not that it is coded as an integer. Regardless, I don't really care what we call this page. I just need something to cite on Definition:Computable Real Number, etc. Using a code number is an easy way to generalize recursive functions to other domains and codomains; instead of defining a whole new class of "integer-valued recursive functions," we just have ordinary $\N$-valued functions that are interpreted as integer codes. I fully agree that this naming convention might run into problems, but I don't have any better ideas.

I've been thinking of using the term "X Coding" to universally refer to representing X as a natural number (where X could be Sequence, Integer, URM Program, etc.). On the other hand, "X Encoding" would mean representing X as a finite string over a finite alphabet, usable by Turing machines, etc. So we would have "Natural Number Encoding" as its binary representation.

It's worth noting, though, that we shouldn't really talk about Codings or Encodings collectively. In order for either one to be useful, it has to be "reasonable" in an informal sense. For example, we could define a "coding" for recursive functions where every total function is represented by an even number, and vice versa. We can do similar things with almost any structure to "break" results in computational complexity theory. In the former case, there is actually a formal definition of "reasonableness," called an Admissible Numbering (which I will write up at some point), but in other cases, there's no easy solution. We just have to pick which ones we call "valid" (e.g. representing a graph as an adjacency matrix). Or, do what I plan to do, and just always state which particular coding is in use.

Last note, if the naming convention is okay but this particular page name isn't, we could totally make an exception. Is something like Code Number for Integer acceptable? --CircuitCraft (talk) 00:16, 10 September 2023 (UTC)

Anyone else better able to help here? I'm out of gas. --prime mover (talk) 07:52, 10 September 2023 (UTC)

The renaming is fine. We can revisit the situation as and when we continue to flesh out the various work in the mathematical logic area. --prime mover (talk) 22:29, 10 September 2023 (UTC)