Computable real function

In mathematical logic, specifically computability theory, a function [math]\displaystyle{ f \colon \mathbb{R} \to \mathbb{R} }[/math] is sequentially computable if, for every computable sequence [math]\displaystyle{ \\{x_i\\}_{i=1}^\infty }[/math] of real numbers, the sequence [math]\displaystyle{ \\{f(x_i) \\}_{i=1}^\infty }[/math] is also computable. A function [math]\displaystyle{ f \colon \mathbb{R} \to \mathbb{R} }[/math] is effectively uniformly continuous if there exists a recursive function [math]\displaystyle{ d \colon \mathbb{N} \to \mathbb{N} }[/math] such that, if

[math]\displaystyle{ | x-y| \lt {1 \over d(n)} }[/math]

then

[math]\displaystyle{ | f(x) - f(y)| \lt {1 \over n} }[/math]

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 [math]\displaystyle{ \mathbb{R}^n. }[/math] The generalizations of the latter two need not be restated. A suitable generalization of the first definition is:

Let [math]\displaystyle{ D }[/math] be a subset of [math]\displaystyle{ \mathbb{R}^n. }[/math] A function [math]\displaystyle{ f \colon D \to \mathbb{R} }[/math] is sequentially computable if, for every [math]\displaystyle{ n }[/math]-tuplet [math]\displaystyle{ \left( \\{ x_{i \, 1} \\}_{i=1}^\infty, \ldots \\{ x_{i \, n} \\}_{i=1}^\infty \right) }[/math] of computable sequences of real numbers such that

[math]\displaystyle{ (\forall i) \quad (x_{i \, 1}, \ldots x_{i \, n}) \in D \qquad , }[/math]

the sequence [math]\displaystyle{ \\{f(x_i) \\}_{i=1}^\infty }[/math] is also computable.

## 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=98745"