Definition
Effectively Computable Function
A partial function
is effectively computable if a procedure satisfying the requirements of effective computation computes exactly its values: for every input tuple and every , Here,
is the domain on which is defined. The procedure returns the correct value on this domain; outside it, the procedure produces no result and may run indefinitely. Total function
If
, the procedure must halt and return on every input . The Church–Turing thesis identifies effectively computable functions with those computable by a Turing machine.