Effective Computability Definition/Meaning:
Let
N = {0,1....}
Nk = N x ... x N
(with k factors)
A function
ƒ : Nk
→ N
is effectively computable only in the case when there is an effective procedure
(i.e. an algorithm) that correctly calculates ƒ An effective procedure is one
that meets the
following specifications. Firstly, the procedure must consist of a finite set of
"simple" instructions (i.e. a program) and there must be no ambiguity concerning
the order in which the instructions arc to be carried out (see Turing machine).
Secondly, if the procedure is given a k-tuple x in the domain of
ƒ, then after a
finite number of steps, the calculation must terminate and output
ƒ(x); if the
procedure is given a A-tuple not in the domain of ƒ it must not output a value.
|
