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 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 X s.t. [(A,n) \in \Phi]\}.

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