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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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
  1. ^ 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.

Provenance

snapshot enwiki-001372299371 · captured 1788143969.0 · version history

Cite this page as: encyclopegia.org, “Computable real function”, snapshot enwiki-001372299371. https://encyclopegia.org/a/computable-real-function