Computable real function
In mathematical logic, specifically computability theory, a function f: \R \to \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.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 primitive recursive function d:ℕ→ℕ such that, if |x−y|<1/d(n), then |f(x)−f(y)|<1/n.
A real function is thus computable if it is both sequentially computable and effectively uniformly continuous.[1]
These definitions can be generalized to functions of several variables as follows: let D be a subset of ℝn. A function f:D→ℝ is sequentially computable if, for every n-tuple ({xi1}i=1∞,…,{xin}i=1∞) of computable sequences of real numbers such that
- (xi1,…xin)∈D
for all i, the sequence {f(xi)}i=1∞ is also computable.
References
edit edit source- ^ Grzegorczyk, A. (1957). "On the definitions of computable real continuous functions" (PDF). Fundamenta Mathematicae. 44 (1): 61–77. Zbl 0079.24801.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1372299371 under CC BY-SA 4.0; modifications have been made.