effective computability

views updated

effective computability Let N = {0,1,…} Nk = N × … × N (with k factors)

A partial function f : NkN

is effectively computable if there is an effective procedure or algorithm that correctly calculates f. An effective procedure is one that meets the following specifications. Firstly, the procedure must consist of a finite set of “simple” instructions and there must be no ambiguity concerning the order in which the instructions are to be carried out. Secondly, if the procedure is given a k-tuple x in the domain of f, then after a finite number of steps, the calculation must terminate and output f(x); if the procedure is given a k-tuple not in the domain of f it must not output a value. See also Church–Turing thesis.