Lower semicomputable function

From Machinelearning
Revision as of 05:48, 25 July 2019 by IssaRice (talk | contribs)

A function f:X→R is lower semicomputable iff there exists a computable function g:X×N→Q such that:

  • for all x∈X and all natural numbers n, we have g(x,n+1)≥g(x,n)
  • for all x∈X we have limn→∞g(x,n)=f(x)

The way to think of this is that given some fixed x∈X, the values g(x,0),g(x,1),g(x,2),… are successive approximations of the value f(x), and we have g(x,0)≤g(x,1)≤g(x,2)≤⋯≤f(x).