Talk:Gödel numbering for sequences

Need definition of ${\overline {n}}$

${\overline {n}}$ denotes $\{0,\dots ,n-1\}$ here? It's not so widely accepted notation, thus we way want to provide a definition for it. しんのすけ代表 (talk) 03:56, 5 March 2020 (UTC)

What its mean

What is it "$\ \!\mathrm {rem}$"? —Preceding unsigned comment added by 77.124.183.77 (talk) 06:10, 9 July 2009 (UTC)

Thank You very much. Sorry for that I did not notice the comment before now. I have just added the required explanatory text: a new subsection "Remainder for natural numbers".

Ergonomic?

What does "more ergonomic approach" (paragraph 3 in the current version) mean? -- Walt Pohl (talk) 14:05, 18 November 2009 (UTC)

Also, what's an "alien object"? -- Walt Pohl (talk) 14:08, 18 November 2009 (UTC)

Section about Gödel's β function is not appropriate here

I think the (very long) section about Gödel's β function does not belong in this article. For one thing, Gödel's β function does not encode a finite sequence of integers into one integer but rather decodes two integers (and an implicit length indication) into a finite sequence of values. But more to the point, the focus of Gödel's β function is not to encode sequences into numbers for the purpose of algorithmic manipulation at all. When that is necessary, Gödel encodes sequences as exponents in a prime factorization instead, which (although computationally expensive) allows straightforward algorithmic encoding and decoding.

However Gödel (still) needs his β function separately as a tool when considering arithmetic definability. When considering arithmetically definable sets, one has at the basis polynomial expressions as a means to define sets, not algorithms. Then in order to show that nevertheless (graphs of) primitive recursive functions are arithmetically definable, one needs a means to express the fact that a given graph satisfies a certain primitive recursive relation, which naturally involves a relation of any point of the graph with the full set of previous points in the graph. Finitely quantified arithmetic formulas cannot directly refer to that whole set of previous values, but thanks to the β function, quantification over just two integers will suffice to get the same result as quantification over such sequences. All that is necessary is that the β function is sufficiently flexible to, by appropriately fixing the first two arguments, produce arbitrary finite sequences of values when varying its third argument. However it must also be obviously arithmetically definable (without having to use the fact that all primitive recursive functions are), and this is why encoding by prime factorization won't do in this context. Once it is proved that the β function has this flexibility, there is no need to actually compute those two values that encode for a given finite sequence, since there will be quantification over all pairs of natural numbers for its first two arguments.

So unless somebody argues strongly to the contrary, I will remove the unhelpful parts of this article (maybe move some useful parts not already there to the beta function page), and replace them by the discussion of a simple encoding by pairing scheme, which for algorithmic purposes suffices, while being much more transparent. Marc van Leeuwen (talk) 15:54, 6 February 2012 (UTC)

I think it makes the most sense for this article to focus on several different ways of encoding sequences. The Β function is one (since there are polynomial bijections that can reduce two numbers to a single number), the prime power coding is another, and there are probably others in computer science. — Carl (CBM · talk) 16:23, 6 February 2012 (UTC)

External links modified

Hello fellow Wikipedians,

I have just added archive links to one external link on Gödel numbering for sequences. Please take a moment to review my edit. If necessary, add {{cbignore}} after the link to keep me from modifying it. Alternatively, you can add {{nobots|deny=InternetArchiveBot}} to keep me off the page altogether. I made the following changes:

• Added archive https://web.archive.org/20061208151518/http://www.math.chalmers.se:80/~rjmh/Papers/whyfp.html to http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 20:30, 19 February 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Gödel numbering for sequences. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20061208151518/http://www.math.chalmers.se/~rjmh/Papers/whyfp.html to http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 22:54, 26 October 2017 (UTC)

Why so verbose ?

I don't get why the part on coprimality of the moduli $m_{i}=im+1,1\leqslant i\leqslant n$ has to be so unnecessarily formal. The whole "Proof that (coprimality) assumption for Chinese remainder theorem is met" section can be made a one-liner. Why not just say :

If $m$ is divisible by $1,\dots ,n$ then the $m_{i}$ are pairwise coprime.

Proof. Suppose a prime $p$ divides $m_{i},m_{j}$ for some $1\leqslant i<j\leqslant n$. Then $p$ divides $m_{j}-m_{i}=(j-i)m$, so $p$ divides $j-i$ or $m$. Since it divides $m_{i}=im+1$, it cannot divide $m$, so it must divide $j-i$. But $j-i$ is an integer between $1$ and $n$, so $p$ divides $m$, contradiction. 37.166.24.201 (talk) 08:59, 29 November 2023 (UTC)