computable real function

A function $f:ℝ\to ℝ$ is sequentially computable if, for every computable sequence ${\{x_i\}}_{i=1}^{\mathrm{\infty }}$ of real numbers, the sequence ${\{f(x_i)\}}_{i=1}^{\mathrm{\infty }}$ is also computable.

A function $f:ℝ\to ℝ$ is effectively uniformly continuous if there exists a recursive function $d:\mathbb{N}\to \mathbb{N}$ such that, if

then

A real function is computable if it is both sequentially computable and effectively uniformly continuous.

It is not hard to generalize these definitions to functions of more than one variable or functions only defined on a subset of ${ℝ}^n$. The generalizations of the latter two definitions are so obvious that they need not be restated. A suitable generalization of the first definition is:

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

$$(\forall i)\mathit{\hspace{1em}}(x_{i\mathrm{\hspace{0.17em}1}},\mathrm{\dots }{x}_{in})\in D\mathit{\hspace{1em}\hspace{1em}},$$

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

Title	computable real function
Canonical name	ComputableRealFunction
Date of creation	2013-03-22 14:39:23
Last modified on	2013-03-22 14:39:23
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	6
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 03F60
Defines	sequentially computable
Defines	effectively uniformly continuous
Defines	effective uniform continuity