Computable real function

In mathematical logic, specifically computability theory, a function f:ℝ->ℝ is sequentially computable if, for every computable sequence {xi}i=1∞ of real numbers, the sequence {f(xi)}i=1∞ is also computable.

A function f:ℝ->ℝ is effectively uniformly continuous if there exists a recursive function d:ℕ->ℕ such that, if

|x−y|<1d(n)

then

|f(x)−f(y)|<1n

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 ℝ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 ℝn. A function f:D->ℝ is sequentially computable if, for every n-tuplet ({xi1}i=1∞,…{xin}i=1∞) of computable sequences of real numbers such that

(∀i)(xi1,…xin)∈D,

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

1. ↑ see Grzegorczyk, Andrzej (1957), "On the Definitions of Computable Real Continuous Functions" (PDF), Fundamenta Mathematicae 44: 61–77, http://matwbn.icm.edu.pl/ksiazki/fm/fm44/fm4415.pdf

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Computable real function. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Computable_real_function&oldid=4157548"