Jump to content

Computable real function

From Wikipedia, the free encyclopedia

In mathematical logic, specifically computability theory, a function is sequentially computable if, for every computable sequence of real numbers, the sequence is also computable.

A function is effectively uniformly continuous if there exists a recursive function such that, if

then

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 The generalizations of the latter two need not be restated. A suitable generalization of the first definition is:

Let be a subset of A function is sequentially computable if, for every -tuplet of computable sequences of real numbers such that

the sequence 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