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

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