Computable real function

In mathematical logic, specifically computability theory, a function $f \colon \mathbb{R} \to \mathbb{R}$ is sequentially computable if, for every computable sequence $\{x_{i}\}_{{i=1}}^{\infty }$ of real numbers, the sequence $\{f(x_{i})\}_{{i=1}}^{\infty }$ is also computable.

A function $f \colon \mathbb{R} \to \mathbb{R}$ is effectively uniformly continuous if there exists a recursive function $d\colon {\mathbb {N}}\to {\mathbb {N}}$ such that, if

$|x-y|<{1 \over d(n)}$

then

$|f(x)-f(y)|<{1 \over n}$

A real function is computable if it is both sequentially computable and effectively uniformly continuous,^[1]

These definitions can be generalized to functions of more than one variable or functions only defined on a subset of ${\mathbb {R}}^{n}.$ The generalizations of the latter two need not be restated. A suitable generalization of the first definition is:

Let $D$ be a subset of ${\mathbb {R}}^{n}.$ A function $f\colon D\to {\mathbb {R}}$ is sequentially computable if, for every $n$ -tuplet $\left(\{x_{{i\,1}}\}_{{i=1}}^{\infty },\ldots \{x_{{i\,n}}\}_{{i=1}}^{\infty }\right)$ of computable sequences of real numbers such that

$(\forall i)\quad (x_{{i\,1}},\ldots x_{{i\,n}})\in D\qquad ,$

the sequence $\{f(x_{i})\}_{{i=1}}^{\infty }$ is also computable.

This article incorporates material from Computable real function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

References

↑ see Grzegorczyk, Andrzej (1957), "On the Definitions of Computable Real Continuous Functions" (PDF), Fundamenta Mathematicae, 44: 61–77

This article is issued from Wikipedia - version of the 5/9/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.