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.

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.



Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Computable analysis — In mathematics, computable analysis is the study of which parts of real analysis and functional analysis can be carried out in a computable manner. It is closely related to constructive analysis. Basic results The computable real numbers form a… …   Wikipedia

  • Computable number — In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a… …   Wikipedia

  • Computable function — Total recursive function redirects here. For other uses of the term recursive function , see Recursive function (disambiguation). Computable functions are the basic objects of study in computability theory. Computable functions are the formalized …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • Real number — For the real numbers used in descriptive set theory, see Baire space (set theory). For the computing datatype, see Floating point number. A symbol of the set of real numbers …   Wikipedia

  • Dehn function — In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group (that is a freely reduced word in the …   Wikipedia

  • Ramp function — The ramp function is an elementary unary real function, easily computable as the mean of its independent variable and its absolute value.This function is applied in engineering (e.g., in the theory of DSP). The name ramp function can be derived… …   Wikipedia

  • Primitive recursive function — The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the recursive functions (recursive functions are also known as computable functions). The term was coined by… …   Wikipedia

  • Ackermann function — In recursion theory, the Ackermann function or Ackermann Péter function is a simple example of a general recursive function that is not primitive recursive. General recursive functions are also known as computable functions. The set of primitive… …   Wikipedia

  • Definable real number — A real number a is first order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds in the standard… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.