Talk:Kleene's recursion theorem

First recursion theorem

I removed an "expert" tag from this section (ignoring whether the tag is well named). Not sure exactly what sort of accessibility is intended – the subsection of the SEP entry [1] does not even state the theorem, and overall is pretty content-free. This article is not the place for us to go into great depths about enumeration operators, any more than it is the place for us to go into details about computable functions. A longer description of enumeration operators could to go in the article on enumeration reducibility, which unfortunately does not exist. — Carl (CBM · talk) 02:07, 22 August 2009 (UTC)

It's true that SEP doesn't state the theorem (Odifreddi dumbed it down for a general audience there), but "Provides a basic tool to find explicit solutions to recursive equations, implicitly defining programs of recursive functions by circular definitions involving the program itself" as an introductory statement seems more accessible to me compared to "The first recursion theorem is related to fixed points determined by enumeration operators, which are a computable analogue of inductive definitions." You could introduce the operators in a 2nd sentence reserve the first for the reader that wants the general picture. By the way, {{intro-tooshort}} applies here too, but I won't tag it since you're probably reading this. I was trying to find some place to redirect recursive equation to that won't produce a big huh from the reader... Pcap ping 02:30, 22 August 2009 (UTC)

P.S. I know that the theorem has two parts, but if Odifreddi thinks the lay reader should recall only the second part, we could introduce it that way too, rather than keep the 1st sentence vague for the sake of not leaving anything out. Pcap ping 02:32, 22 August 2009 (UTC)

Have you read the entire article? The article does start with the second theorem, points out it is more well known, and gives a full example in that context. The section on the second recursion theorem also explains that the main role of the first recursion theorem is to get least fixed points, while the second recursion theorem may give larger fixed points. I can add an example to the section on the first recursion theorem as well. — Carl (CBM · talk) 02:40, 22 August 2009 (UTC)

codomain of enumeration operators?

In the section on First Recursion Theorem, it says,

"Each enumeration operator Φ determines a function from sets of naturals to sets of naturals given by

  $\Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.$

"

but then it also says, "A recursive operator is an enumeration operator that, when given the graph of a partial recursive function, always returns the graph of a partial recursive function."

Graphs of functions are pairs, not naturals. I assume from this and from the example below that the n in the definition of $\Phi (X)$ is a pair of naturals.

The wording "Each enumeration operator Φ determines a function from sets of naturals to sets of naturals given by" makes me think that the function $\Phi (X)$ is a function from sets of naturals to sets of naturals, when in fact it seems to be a function from sets of pairs of naturals to sets of pairs of naturals.

In addition the symbol $\Phi$ appears to be filling a dual role as a set and as a function.

If I am interpreting this correctly, then I suggest changing the wording to something like:

"Each enumeration operator Φ is a set of pairs each of the form $(A,(b,c))$, where $A$ is a graph of a partial function, and $(b,c)$ is an element of the graph of a partial function. We also use the symbol Φ to represent a function on graphs of partial functions defined as:

 $\Phi (X)=\{n\mid \exists A\subseteq Xs.t.[(A,n)\in \Phi ]\}.$

In addition to identifying Φ with a function on graphs of partial functions, we note that each enumeration operator Φ also determines a different function from sets of naturals to sets of naturals. " Bayle Shanks (talk) 22:16, 7 September 2013 (UTC)

I am sure the issue is likely to come down to the convention of identifying a pair of natural numbers with its Goedel number, so that the graph of a function from N to N becomes a subset of N. I would suggest looking up Rogers' book to see how he defines a enumeration operator, and sticking with his convention. — Carl (CBM · talk) 11:25, 8 September 2013 (UTC)

There are two theorems

The title seems to a misapplication of Wikipedia's rule about no plurals in titles. The article is not about Kleene's recursion theorem, which makes no more sense than a scissor or a trouser, but about a pair of theorems in the same paper. If you must make it singular, make two articles titled respectively "Kleene's first recursion theorem" and "Kleene's second recursion theorem". Vaughan Pratt (talk) 21:38, 22 March 2019 (UTC)

Unexplained lambda calculus notation?

The Kleene's second recursion theorem section gives the theorem as:

The second recursion theorem. For any partial recursive function $Q(x,y)$ there is an index $p$ such that $\varphi _{p}\simeq \lambda y.Q(p,y)$.

I cannot see any explanation for the notation $\lambda y.$ in $\varphi _{p}\simeq \lambda y.Q(p,y)$. After hunting around a bit, I guess it is borrowed from lambda calculus, but there is no prior mention of lambda calculus on the page, so I think many readers will not understand it. Possible ideas to resolve: a) remove the notation and just add something like "(considered as a function of y)" after Q(p,y); b) explain the notation earlier in the section on notation; c) include the (y) argument on the $\varphi _{p}$, i.e. $\varphi _{p}(y)\simeq Q(p,y)$, although then perhaps the $\simeq$ notatation becomes inappropriate? Sorry if the editing of this page is all wrong - it's my first edit... Mjt.darjeeling (talk) 05:05, 18 January 2022 (UTC)