patternMinor
What does 'computable in the limit from above' mean?
Viewed 0 times
thecomputablewhatlimitabovemeandoesfrom
Problem
$H(x)$ is the program size complexity of $x$ for some universal Turing machine $U$. $H$ is not computable, however $H$ is "computable in the limit from above".
From my notes:
i.e the set $\{(x,n) \mid x \in B^*,n \geq 0, H(x) \leq n\}$ is computably enumerable.
Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.
From my notes:
i.e the set $\{(x,n) \mid x \in B^*,n \geq 0, H(x) \leq n\}$ is computably enumerable.
Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.
Solution
To quote Wikipedia/Scholarpedia,
A partial function $f$ from the rational numbers to the real numbers is
upper semicomputable if it is defined by a rational-valued partial
computable function $\phi(x,k)$ with $x$ a rational number and $k$ a
nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and
$\lim_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated
from above.
Further, using the squeeze theorem, we could conclude:
If a function $f$ is both upper semicomputable and lower semicomputable
on its domain, then we call $f$ computable
A partial function $f$ from the rational numbers to the real numbers is
upper semicomputable if it is defined by a rational-valued partial
computable function $\phi(x,k)$ with $x$ a rational number and $k$ a
nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and
$\lim_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated
from above.
Further, using the squeeze theorem, we could conclude:
If a function $f$ is both upper semicomputable and lower semicomputable
on its domain, then we call $f$ computable
Context
StackExchange Computer Science Q#6206, answer score: 2
Revisions (0)
No revisions yet.