Lower semicomputable function: Difference between revisions

Revision as of 05:48, 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)$ .

@@ Line 3: / Line 3: @@
 * for all <math>x \in X</math> and all natural numbers <math>n</math>, we have <math>g(x, n+1) \geq g(x,n)</math>
 * for all <math>x \in X</math> we have <math>\lim_{n\to \infty} g(x,n) = 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>.