go-v.orgcodex
Menu
Page tools

codex · Philosophy

Semicomputable function

In computability theory, a semicomputable function is a partial function f:ℚ→ℝ that can be approximated either from above or from below by a computable function. More precisely, a partial function f:ℚ→ℝ is upper semicomputable, meaning it can be approximated from above, if there exists a computable function ϕ(x,k):ℚ×ℕ→ℚ, where x is the desired parameter for f(x) and k is the level of approximation, such that:

limk→∞ϕ(x,k)=f(x) ∀k∈ℕ:ϕ(x,k+1)≤ϕ(x,k) Similarly, a partial function f:ℚ→ℝ is lower semicomputable if and only if −f(x) is upper semicomputable or equivalently if there exists a computable function ϕ(x,k) such that:

limk→∞ϕ(x,k)=f(x) ∀k∈ℕ:ϕ(x,k+1)≥ϕ(x,k) If a partial function is both upper and lower semicomputable, it is computable.

Wikipedia contributors, "Semicomputable function", Wikipedia, revision 1386031638, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex