Computable real function

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

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

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

then

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

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

( ∀ i ) ( x i 1 , … x i n ) ∈ D , {\displaystyle (\forall i)\quad (x_{i\,1},\ldots x_{i\,n})\in D\qquad ,}

the sequence  { f ( x i ) } i = 1 ∞ {\displaystyle \\{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

[edit]

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

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

P ≟ NP |

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template