Editing Computable function (section)

== Characteristics of computable functions ==

{{main|Algorithm}}

The basic characteristic of a computable function is that there must be a finite procedure (an [[algorithm]]) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a [[compiler]] is able to read instructions in one computer language and emit instructions in another language.

[[Herbert Enderton|Enderton]] [1977] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.
* "There must be exact instructions (i.e. a program), finite in length, for the procedure." Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required.
* "If the procedure is given a ''k''-tuple '''x''' in the domain of ''f'', then after a finite number of discrete steps the procedure must terminate and produce ''f''('''x''')." Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned.
* "If the procedure is given a ''k''-tuple '''x''' which is not in the domain of ''f'', then the procedure might go on forever, never halting. Or it might get stuck at some point (i.e., one of its instructions cannot be executed), but it must not pretend to produce a value for ''f'' at '''x'''." Thus if a value for ''f''('''x''') is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is defined as correct if and only if it produces an outcome.

Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:<!-- must be enumerated for the "#Church–Turing thesis" below-->
# The procedure must theoretically work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.
# The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.
# Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.

To summarise, based on this view a function is computable if:
{{ordered list|list-style-type=lower-alpha
|given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions; 
| it returns such output (halts) in a finite number of steps; and
| if given an input which is not in its domain it either never halts or it gets stuck.
}}

The field of [[Computational complexity theory|computational complexity]] studies functions with prescribed bounds on the time and/or space allowed in a successful computation.