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,see

{{Citation|last=Grzegorczyk|first=Andrzej|title=On the Definitions of Computable Real Continuous Functions|journal=Fundamenta Mathematicae|volume=44|year=1957|pages=61–77|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm44/fm4415.pdf|format=PDF}}

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.

{{PlanetMath attribution|id=6248|title=Computable real function}}

References

{{Reflist}}

Category:Computable analysis

{{mathlogic-stub}}

{{comp-sci-theory-stub}}