Computable real function

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

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

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

then

${\displaystyle |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 ${\displaystyle \mathbb {R} ^{n}.}$ The generalizations of the latter two need not be restated. A suitable generalization of the first definition is:

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

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

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