# Recursive function theory

### From HaskellWiki

EndreyMark (Talk | contribs) (A zero arity case excluded -- arity of the result is undefinable) |
EndreyMark (Talk | contribs) (Reverting ,,zero-arity case excluded'' -- zero arity cases can be fruitful) |
||

Line 21: | Line 21: | ||

:<math>\mathbf 0 = 0</math> |
:<math>\mathbf 0 = 0</math> |
||

− | Question: is the well-known <math>\mathbf{zero}(x)=0</math> approach superfluous? Can we avoid it and use the more simple and indirect <math>\mathbf{0} = 0</math> approach? |
+ | Question: is the well-known <math>\mathbf{zero}(x)=0</math> approach superfluous? Can we avoid it and use the more simple and indirect <math>\mathbf{0} = 0</math> approach, if we generalize operations (especially composition) to deal with zero-arity cases in an appropriate way? |

+ | E.g., <math>\underline\mathbf\dot K^0_1\mathbf0\left\langle\right\rangle = n</math> and <math>\underline\mathbf K^0_1\mathbf0 = n</math>, too? |
||

+ | Does it take a generalization to allow such cases, or can it be inferred? |
||

==== Successor function ==== |
==== Successor function ==== |
||

Line 35: | Line 35: | ||

=== Operations === |
=== Operations === |
||

− | |||

− | Are we allowed to generalize operations (especially composition) to deal with zero-arity cases in an appropriate way? |
||

− | E.g., The arity of <math>\underline\mathbf\dot K^0_n c\left\langle\right\rangle</math> and <math>\underline\mathbf K^0_n c</math> (where <math>c : \mathbb N</math>) turns out to be undefined, so we may exclude such constructs. |
||

− | What about 0-arity cases, when can they be allowed or inferred? |
||

==== Composition ==== |
==== Composition ==== |

## Revision as of 19:16, 23 April 2006

## Contents |

## 1 Introduction

## 2 Plans towards a programming language

Well-known concepts are taken from [Mon:MatLog], but several new notations (only notations, not concepts) are introduced to reflect all concepts described in [Mon:MatLog], and some simplification are made (by allowing zero-arity generalizations). These are plans to achive formalizations that can allow us in the future to incarnate the main concepts of recursive function theory in a programming language.

## 3 Primitive recursive functions

### 3.1 Type system

### 3.2 Base functions

#### 3.2.1 Constant

Question: is the well-known approach superfluous? Can we avoid it and use the more simple and indirect approach, if we generalize operations (especially composition) to deal with zero-arity cases in an appropriate way? E.g., and , too? Does it take a generalization to allow such cases, or can it be inferred?

#### 3.2.2 Successor function

#### 3.2.3 Projection functions

For all :

### 3.3 Operations

#### 3.3.1 Composition

This resembles to the combinator of Combinatory logic (as described in [HasFeyCr:CombLog1, 171]). If we prefer avoiding the notion of the nested tuple, and use a more homogenous style (somewhat resembling to currying):

Let underbrace not mislead us -- it does not mean any bracing.

remembering us to

#### 3.3.2 Primitive recursion

The last equation resembles to the combinator of Combinatory logic (as described in [HasFeyCr:CombLog1, 169]):

## 4 General recursive functions

Everything seen above, and the new concepts:

### 4.1 Type system

See the definition of being *special* [Mon:MathLog, 45]. This property ensures, that minimalization does not lead us out of the world of total functions. Its definition is the rather straightforward formalization of this expectation.

### 4.2 Operations

#### 4.2.1 Minimalization

Minimalization does not lead us out of the word of total functions, if we use it only for *special* functions -- the property of being *special* is defined exactly for this purpose [Mon:MatLog, 45].

## 5 Partial recursive functions

Everything seen above, but new constructs are provided, too.

### 5.1 Type system

Question: is there any sense to define in another way than simply ? Partial constants?

### 5.2 Operations

Their definitions are straightforward.

## 6 Bibliography

- [HasFeyCr:CombLog1]
- Curry, Haskell B; Feys, Robert; Craig, William: Combinatory Logic. Volume I. North-Holland Publishing Company, Amsterdam, 1958.
- [Mon:MathLog]
- Monk, J. Donald: Mathematical Logic. Springer-Verlag, New York * Heidelberg * Berlin, 1976.