Talk:General recursive function: Difference between revisions

Revision as of 08:03, 24 February 2020

Latest revision as of 00:42, 9 March 2024

(29 intermediate revisions by 9 users not shown)

Line 1:

{{Talk header}}

{{maths rating|class=B|priority=Mid|field=foundations}}

{{WikiProject banner shell|class=B|vital=yes|1=

{{WikiProject Mathematics|priority=Mid}}

}}

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

Line 148 ⟶ 152:

:::::I see your point, but I guess nobody would enter "definition of computable functions by μ operator" in a search field. Using "What links here?", I found that the following pages redirect to [[General recursive function]] - maybe one of these would be better suited as original (rather than redirected) title: [[General recursive]] - [[General-recursive]] - [[M-recursive function]] - [[Mu recursive function]] - [[Mu-recursive]] - [[Mu-recursive function]] - [[Partial recursive function]] - [[Recursive function (computability)]] - [[Recursive function theory]] - [[Total recursive function]] - [[Μ recursion]] - [[Μ-recursive function]]. Following your argument, names ending in "recursion" are particularly interesting; e.g. what about [[Recursion (computability)]]?

:::::As a related issue, following your objection to my hasty re-targeting, names ending in "function" should better link to [[Computable function]]. I'm not convinced about that: looking for e.g. "M-recursive function" would end up at [[Computable function]], while looking for "Μ recursion" would end up in [[General recursive function]]; this would be likely to lead to confusion. On the other hand, once the logical sub-section relation is made clear, a user ending up in [[General recursive function]] will easily find the way to the more general [[Computable function]] is it's that (s)he was looking for. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 08:03, 24 February 2020 (UTC)

Two basic comments: firstly, if the common terminology is not formally correct, we must not change it to a teminology that is more correct. Secondly, the theory of computability is independent of modern set theory [[ZFC]]. It is often manipulated in other logical frameworks, such as [[intuitionistic logic]]. Therefore, this article must avoid to be too much dependent on set theory. This is for this reason that I have edited the lead for removing the word "class" from the first sentence. It is also a reason for opposing to the merge, as [[Computable function]] is about a set or class of functions, while this article is about individual functions.

Also, there is some ambiguity in the literature whether a (general) recursive funtion is a function that ''can be defined'' by a recursive process or is the pair of a function and a recursive process. Clearly it is the second interpretation that must be preferred, as otherwise the following theorem would be nonsensical: "There are general recursive functions such that it is computationally undecidable whether they equal the constant function zero." As this ambiguity is common in the literature, it is not our job to avoid it in the article title, although the content of the article could deserve to be edited for clarifying this point, or, at least, avoiding to make the ambiguity confusing.

As the concept described in the article is known either as "general recursive function" or "μ-recursive function" but has no commonly used other names, the article title must be one of these two names, and changing it would be [[WP:OR]]. My move from the latter title to the former one could be discussed, but the former name seems more common, specially when used outside the theory of recursive functions. Also, the latter title appears in the search engine as

"M-recursive function", which is confusing, as it may be difficult for the reader to understand that "M" means "μ". [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 11:59, 24 February 2020 (UTC)

:This is a bit of a multithreaded discussion with a lot of facets, which is always hard to keep track of. Let me try a bulleted list and see if that helps.

:*Thanks {{u|Jochen Burghardt}} for pointing out the redirect [[μ recursion]]. I think that's a better title for this article than any so far proposed (though there might be still better options; e.g. I would probably prefer [[μ-recursion]] with the hyphen). The reason is that we seem to be agreed that this article is about a model of computation, and μ-recursion is a model of computation.

:*I agree with {{u|D.Lazard}} that we can't make up our own names for things; if a name is standard in the literature then we use it. However I am skeptical that "general recursive function" truly standardly refers to the model of computation we're discussing, as opposed to the functions thereby computed. I also think that anywhere "general recursive function" is likely to be linked from, or most of the searches for it, will be more usefully served by finding an article about the functions rather than the model of computation.

:*Therefore [[general recursive function]], [[total recursive function]], and all similar phrases with "function" as the [[head (linguistics)|head]], should point to [[computable function]].

:*The fact that the μ gets capitalized in lists is unfortunate, but the damage is limited by the fact that this article is very rarely the first one a reader should be searching for. ''Most'' times, the reader will be better served by reading [[computable function]] first. Only if he/she truly wants to know ''specifically'' about this model of computation is this the right article, and in that case hopefully he/she can find it via a link from another article.

:*I agree that we aren't talking about set theory — for "class of functions" substitute "kind of function", if you like. The kind of function computed by the various models are all the same, and are treated at [[computable function]]. The differences in model of computation are "implementation details", like different programming languages if you will.

:*The point about including the computation as part of the function in some sense is generally well-taken, but doesn't really change anything in this discussion. The computation that computes a given function can be effectively translated between different models of computation in a completely stereotyped way, and you can prove using very mild assumptions (and I'm pretty sure, even in intuitionistic logic) that they compute the same function. Therefore we can still speak of whether a computable function is provably total (for example) without worrying about which model of computation is used.

:Well, that's a lot, better stop here. The big takeaway is we should move this content to a name that clearly names a model of computation, for example [[μ-recursion]], and all the "function" links should point at [[computable function]]. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 21:18, 24 February 2020 (UTC)

== Could "partial recursive function" please be clarified? ==

I'm removing this edit request because I looked it up in a textbook. I'll make a small clarification. [[User:TricksterWolf|TricksterWolf]] ([[User talk:TricksterWolf|talk]]) 13:16, 14 February 2021 (UTC)

== Total Recursive Function redirects here. ==

Total Recursive Function redirects here, and it should not. Total recursive functions are functions that always halt, and this article is about general functions (or partial functions) that may or may not halt. The concept of 'total functions' is very interesting in itself and deserves its own article, so if 'total recursive function' means 'total function' then 'total recursive function' should redirect there. If it doesn't mean that then maybe it should get its own article. [[User:Comiscuous|Comiscuous]] ([[User talk:Comiscuous|talk]]) 06:02, 7 April 2021 (UTC)

:I think the redirect is OK, but it (currently) may be confusing.

:In Wikipedia, there are many redirects of subtopics to more general topics. The most recent example I remember is [[Harvard minimizing chart]] redirecting to [[Logic optimization]], although the former is one of the lesser-known logic optimization methods.

:To reduce the amount of confusion, we should add a section "Total recursive function" and link [[Total recursive function]] to [[General recursive function#Total recursive function]]. This would make clear that the redirect concerns a special case. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 09:44, 7 April 2021 (UTC)

:{{done}} I started a section as suggested, and re-targeted [[Total recursive function]] to there. Please help me in fleshing-out the new section. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 09:59, 7 April 2021 (UTC)

I want to renew my point above that this article is misnamed for the content. The content is about a model of computation, whereas the name appears to be about a kind of function. I still think the best title for this content is [[μ-recursion]] (yes, I'm aware it looks like M-recursion in lists; that's unfortunate but I think it's still the right name). --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 19:09, 7 April 2021 (UTC)

:The title of the article is the name given by the inventor(s) of the concept, and used by many textbooks. Wikipedia cannot and must not change this. Moreover, all the content is about a class of functions. The article is thus not misnamed, as named with a common name of these functions. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 20:17, 7 April 2021 (UTC)

::No, the content is not about a class of functions. The class of functions is the [[computable function]]s, which are defined in several different ways, all provably equivalent and mechanically inter-translatable. This article is about one such way, not about a different class of functions. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 20:22, 7 April 2021 (UTC)

:::No, no, no. The article defines "general recursive functions" or "mu-recursive functions", and the first section is devoted to their definition. This defines a class of functions, which is the main subject of the article. This is a remarkable result (supporting [[Church–Turing thesis]]) that every tentative for an acceptable definition of computable functions leads to the same class of functions. This does not change the fact that this is a class of functions that is defined here. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 20:54, 7 April 2021 (UTC)

::::The class of functions should have a single article, no matter which model of computation is used. The natural (post-Soare) name for that class is "computable function", and that is where the content regarding the class of functions (as opposed to this specific definition/model) should reside. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 20:57, 7 April 2021 (UTC)

::::(By the way, the Church–Turing thesis is not really relevant to this discussion. In the post-Soare era, the term "computable function" no longer means "informally computable function". It means "function obtained in one of these precise and provably equivalent ways". The Soare redefinition of "computable" makes it a little harder to ''state'' the Church–Turing thesis, because there's no longer a convenient phrase for "informally computable function". In my view that's a ''little'' unfortunate, but there's not much we can do about it; this is the nomenclature as it has evolved.) --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 21:03, 7 April 2021 (UTC)

I now see that I had misunderstood D.Lazard's position a bit. I thought he wanted the article to be about functions using this specific model of computation, but give it a name that makes it look like a class of functions. Instead it appears (unless I've misunderstood again, which is certainly possible) that he wants this to be the general article about the class of functions, and he just wants to pick one definition.<br />I see two problems with that. First, I don't see any reason in that case to privilege the definition by &mu;-recursion. It's the most ''traditional'', perhaps the ''oldest'', but it's not really the most perspicuous.<br />The other main problem is that it ignores the Soare-renaming, which I am given to understand has now become almost entirely standard.<br />So my view is still what I said above, with the refinement that the [[computable function]] article needs to be somewhat revised to be about the precise class of functions, and not about "informally computable functions". --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 22:58, 7 April 2021 (UTC)

:I'm not sure I understood all subtleties of your above discussion. Anyway, a look at [[Regular language]], [[Regular grammar]], [[Regular expression]], [[Nondeterministic finite automaton]], [[Deterministic finite automaton]] might be inspiring for the problem we have here. The first article is about the language class, each of the remaining ones is about one particular mechanism to describe class members (all mechanisms lead to the the same class). Of course, e.g. [[Deterministic finite automaton]] speaks about the mechanism (automaton definition) and the result of using it (languages accepted by a DFA); however, general properties of the latter are outsourced to the [[Regular language]] article. I think the situation is quite similar here. Following that scheme, a title "&mu;-recursion" would be preferred about "&mu;-recursive function", but the article would speak about both. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 14:26, 8 April 2021 (UTC)

::What I'm saying is, the analogue of the [[regular language]] article is or should be called [[computable function]], not "general recursive function". That's the effect of the linguistic shift led by Soare in, I think, the nineties? or the aughts at latest. It is quite standard by now. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 16:42, 8 April 2021 (UTC)

:::{{ping|Trovatore}} Thanks, that helped me to understand your above discussion with {{u|D.Lazard}}. I cannot comment on a linguistic shift, since I'm not a native English speaker, and, even worse, were forced to work as an applied computer scientist who had no professional contact with computability theory. However, after re-reading the above discussion, I'd be in favor of following the "Regular language" scheme: having a "main" article named after the function class ("Computable function" or "General recursive function" or similar; note that the "regular" in "regular" language originated from one of its defining mechanisms, see the last paragraph of [[Regular language#Equivalent formalisms]]), having one article for each of the equivalent defining mechanisms, named after the mechanism (e.g. "Lambda calculus", rather than "Lambda-definable function"), moving as much common stuff to the "main" article (including brief discussion of the Church-Turing thesis). My impression is that the editing effort to achieve such a structure would be minimized if we start from the current [[Computable function]] (possibily renamed) as "main", and the articles linked under [[Computable function#Definition]] as "subordinate"; this implies my favor for renaminig [[General recursive function]] to (e.g.) [[&mu;-recursion]], to refer to the defining mechanism, not the function class. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 18:46, 8 April 2021 (UTC)

:::: Yes, I agree. Frankly [[computable function]] is in a bit better state than this article at the current time. This article is mostly the definition and some syntax for the definition. There are three brief sections that are about the functions; they could be moved to [[computable function]]. At the [[computable function]] article, we should make sure there's content about normal forms, closure properties, where the functions sit between generalizations (computability relative to [[oracle machine|oracles]], for example) and finer analysis (for example the [[polynomial hierarchy]]).

:::: And my current thought is that [[&mu;-recursion]] is indeed the best name for "this" article, meaning the article that discusses this particular definition/model of computation. I'm open to other suggestions as long as they don't have the word "function" as the [[head (linguistics)|head]]. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 18:08, 9 April 2021 (UTC)

=== Related discussion ===

Note that there is a related discussion at [[Wikipedia talk:WikiProject Mathematics#Proposal: change terminology from "recursive" to "computable"]]. --[[User:Trovatore|Trovatore]] ([[User talk:Trovatore|talk]]) 05:14, 23 April 2021 (UTC)