Lower semicomputable function - Revision history

IssaRice at 06:03, 25 July 2019

2019-07-25T06:03:00Z

← Older revision		Revision as of 06:03, 25 July 2019
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> 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>		* for all <math>x \in X</math> we have <math>\lim_{n\to \infty} g(x,n) = f(x)</math>

			(i think X might have to be a recursive set)

	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>.

IssaRice at 06:00, 25 July 2019

2019-07-25T06:00:21Z

← Older revision		Revision as of 06:00, 25 July 2019
Line 11:		Line 11:

	Lower semicomputability can be characterized using the idea of recursive enumerability as follows: <math>f : X \to \mathbf R</math> is lower semicomputable if and only if the set <math>\{(x,q) \in X \times \mathbf Q : f(x) > q\}</math> is recursively enumerable.		Lower semicomputability can be characterized using the idea of recursive enumerability as follows: <math>f : X \to \mathbf R</math> is lower semicomputable if and only if the set <math>\{(x,q) \in X \times \mathbf Q : f(x) > q\}</math> is recursively enumerable.

			Examples:

			* Every computable function is lower semicomputable (Why?)
			* Kolmogorov complexity?

IssaRice at 05:58, 25 July 2019

2019-07-25T05:58:40Z

← Older revision		Revision as of 05:58, 25 July 2019
Line 9:		Line 9:

	If we do not know the value of <math>f(x)</math> in advance, it is not possible to tell in general how far away <math>g(x,n)</math> is from <math>f(x)</math>. We would know that <math>g(x,1000)</math> is at least as close to <math>f(x)</math> as <math>g(x,100)</math>, but it's not clear how much closer. In contrast, if a function is both lower and upper semicomputable, then we would have an approximation from above, say <math>h(x,n)</math>. Then <math>g(x,n) \leq f(x) \leq h(x,n)</math>, so we have an estimate that is off by at most <math>h(x,n)-g(x,n)</math>.		If we do not know the value of <math>f(x)</math> in advance, it is not possible to tell in general how far away <math>g(x,n)</math> is from <math>f(x)</math>. We would know that <math>g(x,1000)</math> is at least as close to <math>f(x)</math> as <math>g(x,100)</math>, but it's not clear how much closer. In contrast, if a function is both lower and upper semicomputable, then we would have an approximation from above, say <math>h(x,n)</math>. Then <math>g(x,n) \leq f(x) \leq h(x,n)</math>, so we have an estimate that is off by at most <math>h(x,n)-g(x,n)</math>.

			Lower semicomputability can be characterized using the idea of recursive enumerability as follows: <math>f : X \to \mathbf R</math> is lower semicomputable if and only if the set <math>\{(x,q) \in X \times \mathbf Q : f(x) > q\}</math> is recursively enumerable.

IssaRice at 05:55, 25 July 2019

2019-07-25T05:55:37Z

← Older revision		Revision as of 05:55, 25 July 2019
Line 8:		Line 8:
	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>.		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>.

	If we do not know the value of <math>f(x)</math> in advance, it is not possible to tell in general how far away <math>g(x,n)</math> is from <math>f(x)</math>. We would know that <math>g(x,1000)</math> is at least as close to <math>f(x)</math> as <math>g(x,100)</math>, but it's not clear how much closer.		If we do not know the value of <math>f(x)</math> in advance, it is not possible to tell in general how far away <math>g(x,n)</math> is from <math>f(x)</math>. We would know that <math>g(x,1000)</math> is at least as close to <math>f(x)</math> as <math>g(x,100)</math>, but it's not clear how much closer. In contrast, if a function is both lower and upper semicomputable, then we would have an approximation from above, say <math>h(x,n)</math>. Then <math>g(x,n) \leq f(x) \leq h(x,n)</math>, so we have an estimate that is off by at most <math>h(x,n)-g(x,n)</math>.

IssaRice at 05:53, 25 July 2019

2019-07-25T05:53:36Z

← Older revision		Revision as of 05:53, 25 July 2019
Line 7:		Line 7:

	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>.		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>.

			If we do not know the value of <math>f(x)</math> in advance, it is not possible to tell in general how far away <math>g(x,n)</math> is from <math>f(x)</math>. We would know that <math>g(x,1000)</math> is at least as close to <math>f(x)</math> as <math>g(x,100)</math>, but it's not clear how much closer.

IssaRice at 05:50, 25 July 2019

2019-07-25T05:50:33Z

← Older revision		Revision as of 05:50, 25 July 2019
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>.

IssaRice at 05:48, 25 July 2019

2019-07-25T05:48:44Z

← Older revision		Revision as of 05:48, 25 July 2019
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> 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>		* 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>.

IssaRice: Created page with "A function $f : X \to \mathbf R$ is lower semicomputable iff there exists a computable function $g : X \times \mathbf N \to \mathbf Q$ such that: * for..."

2019-07-25T05:38:56Z

Created page with "A function <math>f : X \to \mathbf R</math> is lower semicomputable iff there exists a computable function <math>g : X \times \mathbf N \to \mathbf Q</math> such that: * for..."

New page

A function <math>f : X \to \mathbf R</math> is lower semicomputable iff there exists a computable function <math>g : X \times \mathbf N \to \mathbf Q</math> such that:

* 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>