effective computability
effective computability Let N = {0,1,…} Nk = N × … × N (with k factors)
A partial function f : Nk → N
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.
A partial function f : Nk → N
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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
effective computability