Computable real function information

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.

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

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

Computable real function information

and 23 Related for: Computable real function information

Computable real function

Computable function

Computable number

Computable analysis

Computability theory

Primitive recursive function

Computable set

Hypercomputation

Ackermann function

Computably enumerable set

Turing completeness

Real analysis

Computation in the limit

Halting problem

Enumeration

Programming Computable Functions

Zero of a function

Turing machine

Real computation

Definable real number

Gamma function

Error function

Domain of a function