PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] alternative characterizations of recursive functions (Topic)

The class of recursive functions may be characterized by considerably weaker conditions than those given in the entry “recursive function” of this encyclopaedia. This entry will discuss several such characterizations.

Criteria 2 and 3 in the list may be replaced by the considerably weaker criterion:

2') The successor function $ S \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ defined as $ S(x) = x+1$ is a recursive function.

By means of a pairing function, the definition may be simplified considerably. Using such a function and its inverses, the set of recursive functions of $ m$ variables may be put in one-to-one correspondence with recursive functions of $ n$ variables for any pair of non-zero positive integers $ m$ and $ n$. Hence one can focus attention on recursive functions of a small fixed number of variables. One characterization of recursive functions of not more than two variables is the following:

The class of recursive functions is the smallest class of positive integer valued functions of not more than two positive integers which satisfies the following criteria:

1') The constant function $ c: \mathbb{Z}_+ \to \mathbb{Z}_+$ defined by $ c(x) = 1$ for all $ x \in \mathbb{Z}_+$ is a recursive function.

2') The successor function $ S \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ defined as $ S(x) = x+1$ is a recursive function.

3') The projection functions $ I^1_1 \colon \mathbb{Z}_+ \to \mathbb{Z}_+$, $ I^2_1 \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$, and $ I^2_2 \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$ defined as

$\displaystyle I^1_1 (x) = x$
$\displaystyle I^2_1 (x,y) = x$
$\displaystyle I^2_2 (x,y) = y$
are recursive functions.

4') If $ a \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$, $ b \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$, $ c \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$ , $ d \colon \mathbb{Z}_+ \to \mathbb{Z}_+$, and $ e \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ are recursive functions, then $ f \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$, $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$, and $ h \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$, defined by

$\displaystyle f(x,y) = d(a(x,y))$
$\displaystyle g(x) = a(d(x),e(y))$
$\displaystyle h(x,y) = a(b(x,y),c(x,y))$
are recursive functions.

5') If $ f \colon \mathbb{Z}_+ \to \mathbb{Z}_+$, $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ are recursive functions, then the function $ h \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$ defined by the recursion

$\displaystyle h(n+1,x) = g(h(n,x))$
with the initial condition
$\displaystyle h(0,x) = f(x)$
is a recursive function.

6') If $ f \colon \mathbb{Z}_+^2 \to \mathbb{Z}_+$ is a recursive function then $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function, where $ g(x)$ is defined to equal $ y$ if there exists a $ y \in \mathbb{Z}_+$ such that a) $ f(0, x), f(1, x), \ldots f(y, x)$ are all defined, b) $ f(z, x) = 0$ when $ 1 \le z <y$, and c) $ f(y, x) = 0$, otherwise $ g(x)$ is undefined.

The criterion 5' may be shown to follow from the remaining criteria, and hence it may be dropped.

By further exploiting the marvelous properties of the pairing function, criterion 6' may be replaced by the following:

6”) If $ f \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function then $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function, where $ g(x)$is defined to equal $ y$ if there exists a $ y \in \mathbb{Z}_+$ such that a) $ f(0, x), f(1, x), \ldots f(y, x)$ are all defined, b) $ f(z, x) = 0$ when $ 1 \le z <y$, and c) $ f(y) = x$, otherwise $ g(x)$ is undefined.

The operation introduced in this new criterion is called minimized inversion and will be denoted as $ g = f^{-1}$. Note that there is no conflict with the usual notion of inverse of a function because, if $ f$ is invertible, the minimized inverse of $ f$ is the same as the inverse of $ f$ in the usual sense; otherwise the notion of minimized inverse extends the definition of inverse to a larger class of functions.

Finally, by taking these ideas even further, Czirmaz showed that recursive functions of a single variable had the following simple characterization:

The class of recursive functions is the smallest class of positive integer valued functions of a positive integer which satisfies the following criteria:

1”) The constant function $ c: \mathbb{Z}_+ \to \mathbb{Z}_+$ defined by $ c(x) = 1$ for all $ x \in \mathbb{Z}_+$ is a recursive function.

2”) The successor function $ S \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ defined as $ S(x) = x+1$ is a recursive function.

3”) The function $ Q \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ defined as $ Q(x) = x - \lceil \sqrt{x} \rceil^2$ is a recursive function. In words, $ Q(x)$ is the difference between $ x$ and the largest square number smaller than $ x$.

4”) If $ f \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ and $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ are recursive functions, then $ h \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function, where

$\displaystyle h(x) = f(g(x))$

6”) If $ f \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function then $ g \colon \mathbb{Z}_+ \to \mathbb{Z}_+$ is a recursive function, where $ g(x)$is defined to equal $ y$ if there exists a $ y \in \mathbb{Z}_+$ such that a) $ f(0, x), f(1, x), \ldots f(y, x)$ are all defined, b) $ f(z, x) = 0$ when $ 1 \le z <y$, and c) $ f(y) = x$, otherwise $ g(x)$ is undefined.



"alternative characterizations of recursive functions" is owned by rspuzio. [ full author list (2) ]
(view preamble)

View style:

Also defines:  minimized inversion

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: square, simple, even, invertible, operation, properties, initial condition, projection, constant function, satisfies, number, fixed, focus, integers, positive, one-to-one correspondence, variables, inverses, pairing function, function, successor, characterizations, recursive functions, class
There is 1 reference to this entry.

This is version 8 of alternative characterizations of recursive functions, born on 2004-09-04, modified 2006-10-08.
Object id is 6139, canonical name is AlternativeCharacterizationsOfRecursiveFunctions.
Accessed 2674 times total.

Classification:
AMS MSC: 03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)