effective computability

A Dictionary of Computing | 2004 | 700+ words | Copyright

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

A partial function f : N^k → 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.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "effective computability." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "effective computability." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-effectivecomputability.html

JOHN DAINTITH. "effective computability." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-effectivecomputability.html

Learn more about citation styles