Talk:General recursive function: Difference between revisions

Revision as of 06:44, 8 September 2020

Latest revision as of 00:42, 9 March 2024

(24 intermediate revisions by 7 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 163 ⟶ 167:

:*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)