General recursive function: Difference between revisions

Revision as of 10:01, 13 November 2021

Revision as of 10:04, 13 November 2021

Line 61:

== Symbolism ==

A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following we will abbreviate the string of parameters x₁, ..., x_n is abbreviated as '''x''':

* '''Constant function''': Kleene uses " C{{su|b=q|p=n}}('''x''') = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " const_n( '''x''') = n ":

:: e.g. C{{su|b=13|p=7}} ( r, s, t, u, v, w, x ) = 13

:: e.g. const₁₃ ( r, s, t, u, v, w, x ) = 13

* '''Successor function''': Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:

:: S(a) = a +1 =_def a', where 1 =_def 0', 2 =_def 0 ' ', etc.

* '''Identity function''': Kleene (1952) uses " U{{su|b=i|p=n}} " to indicate the identity function over the variables x_i; B-B-J use the identity function id{{su|b=i|p=n}} over the variables x₁ to x_n:

: U{{su|b=i|p=n}}( '''x''' ) = id{{su|b=i|p=n}}( '''x''' ) = x_i

: e.g. U{{su|b=3|p=7}} = id{{su|b=3|p=7}} ( r, s, t, u, v, w, x ) = t

* '''Composition (Substitution) operator''': Kleene uses a bold-face '''S'''{{su|b=n|p=m}} (not to be confused with his S for "successor" '''!''' ). The superscript "m" refers to the m^th of function "f_m", whereas the subscript "n" refers to the n^th variable "x_n":

:If we are given h( '''x''' )= g( f₁('''x'''), ... , f_m('''x''') )

:: h('''x''') = '''S'''{{su|b=m|p=n}}(g, f₁, ... , f_m )

Line 80:

:: h(''x''')= Cn[g, f₁ ,..., f_m]('''x''')

* '''Primitive Recursion''': Kleene uses the symbol " '''R'''ⁿ(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)('''x''')". Given:

:* base step: h( 0, '''x''' )= f( '''x''' ), and

:* induction step: h( y+1, '''x''' ) = g( y, h(y, '''x'''),'''x''' )

Line 90:

::: Pr{ U{{su|b=1|p=1}}(a), S[ (U{{su|b=2|p=3}}( b, c, a ) ] }

'''Example''': Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starts with 3 initial functions

:# S(a) = a'

:# U{{su|b=1|p=1}}(a) = a