Definition
Partial Computable Function
A partial function
is partial computable (p.c.) if there exists a URM program such that, for every input tuple , and whenever it halts, its output is
. The set
is the domain on which is defined. The program must halt and return the correct value there; outside it, the program never halts. A partial computable function may also be total. Computational model
This definition fixes the URM as its computational model. Using Turing machines instead gives the same class of functions; this equivalence is a theorem.
The Church–Turing thesis identifies this formal class with the effectively computable functions.