Computable real function

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

${\displaystyle |x-y|<\frac{1}{d(n)}}$

then

${\displaystyle |f(x)-f(y)|<\frac{1}{n}}$

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

Let ${\displaystyle D}$ be a subset of ${\displaystyle {\mathbb{ℝ}}^n.}$ A function ${\displaystyle f:D\to \mathbb{ℝ}}$ is sequentially computable if, for every ${\displaystyle n}$-tuplet ${\displaystyle (\{x_{i1}{\}}_{i=1}^{\mathrm{\infty }},\dots \{x_{in}{\}}_{i=1}^{\mathrm{\infty }})}$ of computable sequences of real numbers such that

${\displaystyle (\mathrm{\forall }i)(x_{i1},\dots x_{in})\in D,}$

the sequence ${\displaystyle \{f(x_i){\}}_{i=1}^{\mathrm{\infty }}}$ is also computable.

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Computable real function. Read more