Talk:general recursive function

Mathematics B‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
B	This article has been rated as B-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]