|WikiProject Mathematics||(Rated Start-class, Low-priority)|
|WikiProject Computer science|
Could the Title not be writen as ?
- I don't think so - due to technical restrictions sub- and superscripts are not presently possible. --Kizor 12:07, 24 November 2005 (UTC)
merged version by Math MArtin
Given a Gödel numbering
The following sentences from the scetion "Details" strike me as superfluous.
To generalize the theorem, choose a scheme for encoding n numbers as one number, so that the original numbers can be extracted by primitive recursive functions. For example, one might interleave the bits of the numbers.
In fact, the remainder of the section does not use any encoding scheme for numbers, just the usual Gödel numbering of computable functions.
Another remark: the section "Example" isn't an example at all. LISP is not a language of functions from (tuples of) natural numbers to natural numbers, and certainly not a language of primitive recursive functions. While it can operate on values representing LISP source code, this is not an example of Gödel numbering at all. I think the trivial implementation given is more misleading than illustrative, since the actual proof if the theorem (essentially the construction of the requested primitive recursive function) is far more complicated than the example suggests. Marc van Leeuwen (talk) 13:14, 1 March 2012 (UTC)
Statement of basic form of theorem is confusing
Quote from the article:
Given a Gödel numbering of recursive functions, there is a primitive recursive function s of two arguments with the following property: for every Gödel number p of a partial computable function f with two arguments, the expressions and are defined for the same combinations of natural numbers x and y, and their values are equal for any such combination.
I would rephrase it as follows
Given a Gödel numbering of partial recursive functions, there is a primitive recursive function s of two arguments with the following property: for every Gödel number p of a partial computable (recursive ??) function with two arguments, the expressions and are defined for the same combinations of natural numbers x and y, and their values are equal for any such combination.
(The statement of the more general form of the theorem seems clear to me as it is in the article.) My rationale for this proposed change is that, given the Gödel number of the function f, we can simply express it in terms of its Gödel number without cluttering the reader's mind with an extra variable name. Also the article should standardize terminology, viz. "partial recursive function" vs. "partial computable function". However, I do not want to make these change on my own since I am not an expert in this area. 220.127.116.11 (talk) 00:10, 22 March 2015 (UTC)