Computable real function: Difference between revisions

Revision as of 06:08, 21 December 2011

Latest revision as of 20:47, 27 April 2020

(4 intermediate revisions by 4 users not shown)

Line 1:

In [[mathematical logic]], specifically [[recursion theory|computability theory]], a [[rangefunction (mathematics)|function]] <math>f \colon \mathbb{R} \to \mathbb{R}</math> is ''sequentially computable'' if, for every [[computable sequence]] <math>\{x_i\}_{i=1}^\infty</math> of [[real number]]s, the [[sequence]] <math>\{f(x_i) \}_{i=1}^\infty</math> is also [[computable real number|computable]].

A function <math>f \colon \mathbb{R} \to \mathbb{R}</math> is ''effectively uniformly continuous'' if there exists a [[primitive recursive function|recursive function]] <math>d \colon \mathbb{N} \to \mathbb{N}</math> such that, if

<math> | x-y| < {1 \over d(n)}</math>

then

<math> | f(x) - f(y)| < {1 \over n}</math>

A [[real function]] is ''computable'' if it is both sequentially computable and effectively uniformly continuous.,<ref>see

{{Citation|last=[[Andrzej Grzegorczyk|Grzegorczyk]]|first=Andrzej|title=On the Definitions of Computable Real Continuous Functions|journal=[[Fundamenta Mathematicae]]|volume=44|year=1957|pages=61–77|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm44/fm4415.pdf|format=PDF}}</ref>

These [[definition]]s can be generalized to functions of more than one [[Variable (mathematics)|variable]] or functions only defined on a [[subset]] of <math>\mathbb{R}^n.</math> The generalizations of the latter two need not be restated. A suitable generalization of the first definition is:

Let <math>D</math> be a subset of <math>\mathbb{R}^n.</math> A function <math>f \colon D \to \mathbb{R}</math> is ''sequentially computable'' if, for every <math>n</math>-tuplet <math>\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> (\forall i) \quad (x_{i \, 1}, \ldots x_{i \, n}) \in D \qquad ,</math>

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

{{planetmathPlanetMath attribution|id=6248|title=Computable real function}}

==References==

{{Reflist}}

[[Category:Computable analysis]]

{{mathlogic-stub}}