Computable Partial Function

computation

Definition

Computable Partial Function

A (potentially partial) function $f:X\to Y$ is called computable if there exists an algorithm $A$ with the following properties:

• $A$ takes any $x\in X$ as input
• If $A$ halts on input $x$, it outputs $f(x)$
• $A$ runs forever on input $x$ iff $f$ is not defined at $x$