Talk:General recursive function

This page was a REDIRECT to Talk:Recursive function. Let us have a real talk page instead. JRSpriggs 05:54, 11 August 2006 (UTC)

This article or section may contain too much repetition.

Well DUH its about recursion.

Definition of search operation mu

I brought back the old definition of the search operation because the new one introduced by CMummert is not actually computable. JRSpriggs 06:15, 11 August 2006 (UTC)

My previous definition wasn't very clear; I was using the word function to mean total function. Of course minimization of partial functions is not computable. I saw last week that you had fixed it. Thanks. CMummert 19:15, 13 August 2006 (UTC)

---

χ ψ Ψ ψ φ τ Χ μ ≤ ≥ ≠ → ← Ø ≡ ℛ

Am confused how the 0 as the least number suddenly jumped in here. My question has to do with "the function R" inside the mu-operator -- shouldn't it actually be a representing function of a predicate such that it evaluates to 0 if true and 1 if false?

I figured it out. So I will cut this junk below and save some trees. wvbaileyWvbailey 22:37, 8 November 2006 (UTC)

Defines the same thing as Computable function

To me, the title suggests that the purpose of the article is to define a certain class of functions. However, the same class is already defined in computable function. Wouldn't it make more sense for the title of the article to be "Mu-recursion", since what is unique to this article is that particular definition of "computable function"? Also, is there any reason the article should not be merged with Mu-operator? —The preceding unsigned comment was added by Quux0r (talk • contribs) 2007-04-11T02:14:22.

The idea is that computable function is written so that it is independent of the specific model of computation, and this page is about one particular model of computation. The computable function article does not define this class of functions specifically, it just links here. You could merge this with mu operator but both this page and that page are quite long so it would take a lot of trimming to merge them. I for one would not object to the trimming. You might want to put up merge tags and wait a few days, and/or write the merged version in a sandbox. CMummert · talk 02:20, 11 April 2007 (UTC)

Cleanup needed

This needs some cleanup to be readable. A large part of the article reads like a collection out-of-context snippets from Kleene's book. Pcap ping 05:07, 21 August 2009 (UTC)

Get to work and do it. BillWvbailey (talk) 14:33, 21 August 2009 (UTC)

Minimisation operator and partial functions

I belive that the minimisation operator can only accept total functions, otherwise the recursive functions wouldnt be closed under the minimisation operator.

An example is:

f(x, y) = 0 <==> (y = 0 and x ∈ A) or y = 1

where A is recursively enumerable (but not recursive)

f is partial and is M-recursive.

g (x) = μ y. (f(x,y)=0)

g is total (if it's not 0 then its 1).

g cant be M-recursive, otherwise A would be recursive, since g would be its indicator function (absurd).

I'm going to modify the article, if i'm wrong please state the reason here. — Preceding unsigned comment added by X-Overload-X (talk • contribs) 04:31, 27 June 2011 (UTC)

If A isn't recursive, then f(x,0) is undefined for x not in A. μ operator is also undefined if checked function is partial (as stated here). Then, function g will also be partial and then it can be indicator for non-recursive set. Maybe I am wrong, 'cause I'm not very familiar with μ operator 79.184.100.6 (talk) 17:20, 30 March 2012 (UTC)

Plagiarized Intro?

Sorry if this has been discussed before, but the introduction is identical to https://www.princeton.edu/~achaney/tmve/wiki100k/docs/%CE%9C-recursive_function.html

Which came first?

Also, a cosmetic note: The last line of the intro is very confusing and should be omitted in my opinion, so it's not clear to someone unfamiliar with the material what "recursive function" means in this case. It might easily be thought that "recurisive" is being used here as a synonym for "mu-recursive". This line also seems a bit irrelevant. — Preceding unsigned comment added by Luv2run (talk • contribs) 21:33, 26 October 2012 (UTC)

In a nutshell: the lead paragraph has been stable for 10 years. A bit of research in the history indicates that in May 2002 Axelboldt introduced a significant change in the first two or three sentences, then someone else came along and added the Ackermann function, and etc. You can ask Axelboldt, although I suggest that before spending any time on this and pestering Axelboldt, you should ask yourself the question: who cares? And given the answer: "I really care", then go through "the seven whys" ("Why do you care?" . . . "Because it's academically dishonest [etc]" . . . Why is it academically dishonest? . . . [etc]). BillWvbailey (talk) 23:13, 26 October 2012 (UTC)

The Princeton page says (at the bottom) "The article content of this page came from Wikipedia and is governed by CC-BY-SA." Tijfo098 (talk) 13:18, 12 November 2012 (UTC)

Is There A Contradiction In The Introduction?

The introduction states that all recursive functions are a part of the R class of functions. However; the mu-operator described in this very page is not expected to halt in some conditions, therefore clearly not in R. Am I missing something basic here? - 8 June 2019‎ 185.3.147.227

No, it says the set of all total recursive functions (with values in {0,1}) is R. The restriction "total" means all mu-operators involved in a function definition must eventually halt. - Jochen Burghardt (talk) 16:42, 8 June 2019 (UTC)

For the record, when the question was asked, the last sentence of the lead was wrongly stated, and there was therefore a contradiction between it and the remainder of the lead (thanks to the IP for pointing it). I have fixed this contradiction before Jochen reply, which uses the new formulation. I wrote a reply explaining this, but apparently, I forgot to save it. D.Lazard (talk) 08:31, 9 June 2019 (UTC)

Minimisation operator and partial functions again

It is not required to demand that function f in the definition of the μ-operator is total. The μ-operator can be implemented in any programming language by some code similar to

    μ(f)(x*) <= i := 0; while f(i, x*) > 0 do i := i + 1 end; return(i)

As f is a total and μ-recursive, f(i, x*) > 0 is decidable and consequently μ(f)(x*) is undefined iff f(i, x*) > 0 for each i (as the while-loop then never terminates). Now let

    μ'(f)(x*) <= i := 0; while f(i, x*) > 0 do i := i + 1 end; return(i)

for each (i.e. not necessarily total) function f. μ'(f)(x*) is undefined iff f(i, x*) > 0 for each i (as before) or f(i, x*) is undefined and f(j, x*) > 0 for each j < i (as the test in the while-statement then does not terminate). It is immediately obvious from the definition with the while-loop, that μ'(f) is a computable function, and that μ(f) = μ'(f) if f is total.

Example 1: If f(i, x) computes the residue class of i+1 mod x if x > 0 and is undefined for x = 0, then μ cannot be applied to f. μ'(f)(0) is undefined and μ'(f)(n+1) = n.

Example 2: If f(i) := 42 - i, if i ≤ 42, and f(i) := f(i+1) otherwise, then μ cannot be applied to f. μ'(f) is a total function as μ'(f) = 42.

The definition of μ-recursive functions gives a notation (syntax) for the definition of computable functions, as the syntax of any programming language L does. However, it is decidable whether a certain text defines a program of L (each compiler for L provides a decision procedure). But it is undecible, whether a certain text defines a μ-recursive function because it cannot be decided whether a computable function is total (this is even not semi-decidable in fact). By allowing the minimization of non-total functions, the notation of μ-recursive functions becomes decidable. Jack Rusell (talk) 13:04, 21 November 2019 (UTC)

You are right. This is the reason why, some time ago, I have added (the domain of a function defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result) before the definition of the operators (see above thread). But I forgot to remove "total" in the definition of the μ operator. Now, this is done, and presently the article defines your function μ'. The formulation can certainly be improved, but, getting a formally correct result would needs a much deeper edit. D.Lazard (talk) 15:18, 21 November 2019 (UTC)

Thanks for the update. I have added a note as it may confuse readers when finding the demand for total functions in a textbook (and may also minimize traffic on the talk page). Btw. I do not understand your (the domain of a function ... well-defined result). Can you reformulate to make it understandable (at least for people like me). Jack Rusell (talk) 16:48, 21 November 2019 (UTC)

I have added an explanation in each case. Maybe the quoted sentence may be edited and removed. By the way, there was an edit conflict with your added note. I have tagged it because if some textbooks use the definition with "total", at list one must be cited. Also, as the general recursive functions have been originally defined by Gödel (this must be said in the article), the original definition must be checked. In any case, the assertion that the two definitions lead to the same class of function seems dubious, and, if true, it proof is certainly not easy. D.Lazard (talk) 17:42, 21 November 2019 (UTC)

 Comment: As for the {{citation needed}} after "the class of μ-recursive functions remains the same", I remember the reason: when a Turing machine is converted into an equivalent mu-recursive function, the minimalization needs to be use only a single time, viz. for the outermost loop, informally: while (not in a stop state) do (perform a single machine step) done. The loop body itself can be implemented by a primitive recursive function that looks up the program, writes the new symbol, moves the head, and changes the state. Maybe this helps to find a textbook reference (I just tried, but failed). - Jochen Burghardt (talk) 20:45, 21 November 2019 (UTC)

I just saw that this is mentioned in section μ-recursive function#Normal form theorem; a reference to there should suffice. However, the Kleene theorem there needs a citation in turn. - Jochen Burghardt (talk) 20:47, 21 November 2019 (UTC)

I have provided the required references. However, I was unable to cite without creating a duplicate entry in the reference list (I searched for a while). Maybe you (or someone else) can replace my non-standard citations with the correct command. I also provided references for the "same class" statement. It is obvious that μ-computable entails μ'-computable. I think a direct proof for the opposite needs some work. It is easier to use equivalence proofs, i.e. μ'-computable implies Turing-computable implies μ-computable. I checked my course notes where I proved equivalence of μ'-recursion with a simple while-language. When proving while-computable implies μ'-computable, the μ'-operator is applied to a total function in the proof (the function which evaluates the while-condition), hence my proof works fore the μ-operator as well. As I cannot give a reference to this proof here, I used Kleene's Normalform Theorem as an evidence. (PS: This comment was written before the former comment was, but sended later.) Jack Rusell (talk) 21:12, 21 November 2019 (UTC)

Historical section needed, and other things to do

Thanks to Jochen Burghardt and Jack Rusell for Having fixed my approximative knowledge of the subject. It appears from the preceding discussion that the historical context is completely lacking, although it is fundamental to really understand the subject. It could be provided by a history section where should appear (at least)

• Who introduced the concept, and for which purpose (AFIK, this is Gödel for the purpose of decidability theory, which is now a part of computability theory).
• Equivalence with lambda calculus and Turing machines (AFIK, this is due to Kleene), relationship with Church–Turing thesis.
• History of the terminology (AFIK, "μ-recursive function" is relatively recent, and Kleene used "general recursive function"). I ignore whether Gödel used "general recursive function" or simply "recursive function"). See also next thread.

Such an historical section seems the best way for explaining the choice of not imposing "total" for the minimization operator.

By the way there are many other things that deserve to be added to this article. In particular the section "Equivalence with other models of computability" need to be rewritten and expanded; the assertion that μ-recursive functions and Turing machines are "parallel" theories must be corrected.

Also, examples of μ-recursive functions that are not primitive recursive must be given (Ackermann function). D.Lazard (talk) 15:06, 22 November 2019 (UTC)

For the equivalence, an overview can be found in the Church–Turing thesis in footnote 6. Some snippets of that article's history information may also be useful here. - Jochen Burghardt (talk) 21:48, 22 November 2019 (UTC)

Proposed move

I suggest renaming this article General recursive function. If there is a consensus for that, I have the rights needed for doing the move. The reason for such a move are

• This is a much more common name: Scholar Goofle provides 1230 hits for "General recursive function" (with quotes), while mu-recursive and μ-recursive (without "function") provide 64 and 356 hits, respectively.
• This is the name used by the founders of the theory
• This would make the search easier (this is the reason for which I have created some time ago the redirect General recursive function, after a rather difficult search of the article about this concept).

Clearly a redirect must be kept after moving.

Opinions and comments? D.Lazard (talk) 15:30, 22 November 2019 (UTC)

The theory of computation considers different models of computation, such as Turing machines, μ-recursive functions, the λ-calculus, RAM-machines and more. Common to all models (which are completely different in their definitions) is that they all compute the same functions, i.e. they are equivalent in their computing power. This observation (different notions yields identic results) lead to Church's Thesis. One defines the class of general recursive functions as the class of functions which can be computed by either of these models (of computation). Therefore the title "μ-recursive functions" fits precisely what the article is all about. A title "General recursive functions" would be misleading because the article completely ignores the other models, Turing machines and the λ-calculus at least. For this reason, I suggest not to change the title. Jack Rusell (talk) 17:02, 22 November 2019 (UTC)

My view is that this article should be merged with computable function, because Soare has effectively succeeded in making it standard for "computable" to mean this class of functions, formally definable in a number of provably equivalent ways.
The downside is that it's (a little) harder to explain what Church's thesis actually is, because if computable function means a certain informally defined, intuitively comprehensible class of functions, then you can just say that Church's thesis is the assertion that all computable functions are recursive. If all computable functions are recursive by definition, that doesn't seem to say anything.
But as unfortunate as that might be, that ship has sailed; this is what "computable" means, now. When explaining Church's thesis, we just have to find other language. --Trovatore (talk) 06:56, 23 February 2020 (UTC)

Before Church's thesis, the term "computable function" was informally defined. It is for elaborating a formal definition that general recursive functions, Turing machines and lambda calculus have been introduced. The fundmental theorem that supports Church's thesis is that these three models of computation compute the same functions. So, the modern definition of a "computable function" is a function than can be computed by any of these models of computation (and many others). As each of these models of computation are rather technical to define, many authors focuse on one of them. As far as I understand, general recursive functions are preferred by pure mathematicians and philosophers, because they are closer to their way of thinking. In computational complexity theory, computability is usually defined by Turing machines. In high level programming and semantics (computer science), lambda-calculus is generally preferred, as making easier self referencing computations (universal machines, and functions that define other functions and use them for further computations).

So, I oppose the proposed merge with computable function. This article is about the equivalence between the main models of computation, while General recursive function is about one of them. Merging would make computable function too technical for many readers, who do not need to learn the technical definitions, and, overall would breaks WP:NPOV policy by privileging one theory over the others. D.Lazard (talk) 09:13, 23 February 2020 (UTC)

By the way: Total recursive function currently redirects to Computable function. By D.Lazard's argument, it should better redirect to General recursive function. Any objections? - Jochen Burghardt (talk) 15:29, 23 February 2020 (UTC)

Fine for me. D.Lazard (talk) 16:25, 23 February 2020 (UTC)

 Done Per apparent consensus. - Jochen Burghardt (talk) 22:02, 23 February 2020 (UTC)

I don't actually agree with that, as I mention below (though I made the comment after your change). I think someone linking or searching "total recursive function" is more likely interested in the class of functions, rather than the "implementation-specific" details of how the class is defined. --Trovatore (talk) 22:35, 23 February 2020 (UTC)

It seems to me that, if the article is really about the model of computation rather than the class of functions, then it's misnamed. I'm not sure what the name should be, but it's misleading to name it after a class of functions if it's really about a model of computation.

Also, in that case, this article is much less important than computable function; it's logically just a sub-section of that one. This should be indicated somehow in the article. --Trovatore (talk) 21:16, 23 February 2020 (UTC)

I agree with D.Lazard that General recursive function and computable function should not be merged; it seems that the latter article is long enough by its own, containing only the information common to all models of computation. And I agree with Trovatore that the logical sub-section relation should be made clear. As for the article name, I don't know a better one that is somewhat common in the literature. As a kind of justification, one might say that general recursive functions have domain and range ℕ, while lambda functions operate on lambda terms, and Turing machines operate on strings (or even "tapes"?). The equivalence proofs underlying the Chruch-Turing thesis construct isomorphisms from one function class to another, this is (slightly) more than just establishing mutual subset properties. - Jochen Burghardt (talk) 22:02, 23 February 2020 (UTC)

My concern is that the article appears to be about a class of functions but apparently is not. This is confusing to the reader. It could be moved to a more descriptive title, perhaps definition of computable functions by μ operator or some such. I think total recursive function and general recursive function should point to computable function, as these are synonyms (they didn't use to be, pre-Soare, but they are now). --Trovatore (talk) 22:09, 23 February 2020 (UTC) Oh — "synonyms" except for the "total" bit, of course; that was my goof. --Trovatore (talk) 22:26, 23 February 2020 (UTC)