Talk:Primitive recursive function: Difference between revisions

Revision as of 12:59, 28 February 2024

Latest revision as of 03:36, 9 March 2024

(53 intermediate revisions by 2 users not shown)

Line 1:

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

{{WikiProject Mathematics|priority=Mid|field=foundations}}

}}

Line 309:

::::"In [[recursion theory|computability theory]], the '''primitive recursive functions''' are, roughly speaking, the functions that may be defined and computed by a computer program made up from the arithmetic operations, the ''if then else'' control statement and the ''for i'' = 1 ''to n'' loop (excluding the ''while'' loop with a number of iterations that are is not known when entering in the loop). The primitive recursive functions form an important building block on the way to a full formalization of computability and are important in [[proof theory]]. Historically, and for allowing simpler proofs, they are formally defined using a short list of ways of [[function composition|composing functions]] and a particular form of [[recursion (computer science)|recursion]] known as '''primitive recursion'''. The term was coined by [[Rózsa Péter]]."

:::As almost everybody knows the bases of computer programming this would make the first paragraph understandable for a much wider audience. This characterization of the primitive recursive functions has also the advantage to allow a non specialist to recognize primitive recursive functions by himself. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:02, 2 September 2013 (UTC)

::::If you want to appeal to the man from the street. You could explain primitive recursive as LOOP-programs, and general recursive as WHILE-programs. But I guess [[Computability theory]], also known as recursion theory hasn't taken this road. An early mention of primitive recursive was in Dedekind 1888.

::::[[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 13:05, 28 February 2024 (UTC)

If either of you make any changes to the article, please make them incrementally: make a small (localized) change, wait a few days to see what the reaction is, make another small change, wait a few more days, etc.. This way I or others can correct any errors you introduce instead of having to revert you wholesale. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 02:46, 3 September 2013 (UTC)

Line 388 ⟶ 390:

:Moreover, these sections are not sourced. This could be a reason for removing them as [[WP:OR]].

:So, I have reverted your tag removals. Please do not remove them again without addressing the issues of these sections. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 10:08, 28 February 2024 (UTC)

:: According to [[Second-order_arithmetic]] there is more than one PA. Which might be contextually relevant, since the principia used higher order logic, as noted by Gödel 2.1 Definitions https://hirzels.com/martin/papers/canon00-goedel.pdf

:: [[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 12:33, 28 February 2024 (UTC)

:: Nobody uses the terminology "multivariate" in recursion theory. The term n-ary means a function with n-arguments. The Cantor [[Pairing_function]] can be used to encode two or more arguments in one argument, and its also possible to reverse the process. The function is itself primitive recursive, so are its projections.

:: [[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 23:02, 28 February 2024 (UTC)

About the used references in the article. Instead of Rose as reference for Elimination of Parameters, its seems you could also use Moschovakis 1994, ch. 5.

Or as SEP has put it, they show the other way around from h, to h2 and then to h1, but then have the following remark:

Line 399 ⟶ 404:

[[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 11:44, 28 February 2024 (UTC)

:You do not adress the main issue of these sections. Wikipedia is not for summarizing some specific articles, relying on these articles to know author's definitions of the technical terms. The aim of an encyclopedy is to present the most important results in a language that is compatible with the most common terminology, and is accessible to (in the case of this article) a undergraduate student in mathematics. It must also be clear why a result is important enough to belong to the article (per [[WP:UNDUE]]). Neither the sections under discussion nor your above comments satisfy these requisites. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 14:12, 28 February 2024 (UTC)

::To reduce complexity of the article I would split off Gödel, and I would also split off LOOP/WHILE. Devote separate articles to the two, would make the primitive recursive article more readable and less cluttered with applications of the notion primitive recursive in Gödels theorem and computational devices such as LOOP, that show primitive recursive behaviour.

::[[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 22:41, 28 February 2024 (UTC)

I have deleted the first disputed section,

and move the second disputed section to here:

[[Gödel's β function]]

There I would also like to add a reference to this:

PRIMITIVE RECURSIVE FUNCTIONS by<br>

Zéev Rosenfeld - March 1959<br>

Department of Mathematics McGill University Montreal.

But I don't know how to edit and add a reference.

[[User:Janburse|Jan Burse]] ([[User talk:Janburse|talk]]) 22:51, 28 February 2024 (UTC)