Lower semicomputable function: Difference between revisions

Revision as of 05:50, 25 July 2019

A function $f : X \to R$ is lower semicomputable iff there exists a computable function $g : X \times N \to Q$ such that:

for all $x \in X$ and all natural numbers $n$ , we have $g (x, n + 1) \geq g (x, n)$
for all $x \in X$ we have $lim_{n \to \infty} g (x, n) = f (x)$

The way to think of this is that given some fixed $x \in X$ , the values $g (x, 0), g (x, 1), g (x, 2), \dots$ are successive approximations of the value $f (x)$ , and we have $g (x, 0) \leq g (x, 1) \leq g (x, 2) \leq \dots \leq f (x)$ .

The definition says nothing about the rate of convergence, so for instance if we want $g (x, n)$ to be within $1 / 1000$ of the value of $f (x)$ , there is not in general some way to find a large enough $n$ .

Revision as of 05:48, 25 July 2019 (view source) IssaRice (talk \| contribs) No edit summary ← Older edit		Revision as of 05:50, 25 July 2019 (view source) IssaRice (talk \| contribs) No edit summary Newer edit →
Line 5:		Line 5:

	The way to think of this is that given some fixed <math>x \in X</math>, the values <math>g(x,0), g(x,1), g(x,2), \ldots</math> are successive approximations of the value <math>f(x)</math>, and we have <math>g(x,0) \leq g(x,1) \leq g(x,2) \leq \cdots \leq f(x)</math>.		The way to think of this is that given some fixed <math>x \in X</math>, the values <math>g(x,0), g(x,1), g(x,2), \ldots</math> are successive approximations of the value <math>f(x)</math>, and we have <math>g(x,0) \leq g(x,1) \leq g(x,2) \leq \cdots \leq f(x)</math>.

			The definition says nothing about the rate of convergence, so for instance if we want <math>g(x,n)</math> to be within <math>1/1000</math> of the value of <math>f(x)</math>, there is not in general some way to find a large enough <math>n</math>.