Editing Computable function (section)

==Examples==

The following functions are computable:

* Each function with a finite [[Domain of a function|domain]]; e.g., any finite sequence of natural numbers.
* Each [[constant function]] ''f'' : '''N'''<sup>''k''</sup> → '''N''', ''f''(''n''<sub>1</sub>,...''n''<sub>''k''</sub>) := ''n''.
* [[Addition]] ''f'' : '''N'''<sup>2</sup> → '''N''', ''f''(''n''<sub>1</sub>,''n''<sub>''2''</sub>) := ''n''<sub>1</sub> + ''n''<sub>2</sub>
* The [[greatest common divisor]] of two numbers
* A [[Bézout coefficient]] of two numbers
* The smallest [[prime factor]] of a number

If ''f'' and ''g'' are computable, then so are: ''f'' + ''g'', [[Multiplication|''f'' * ''g'']], [[Function composition|<math>\color{Blue} f \circ g</math>]] if
''f'' is [[Unary operation|unary]], max(''f'',''g''), min(''f'',''g''), {{math|[[arg max]]{{mset|''y'' ≤ ''f''(''x'')}}}} and many more combinations.

The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

* The function ''f'' such that ''f''(''n'') = 1 if there is a sequence of ''at least n'' consecutive fives in the decimal expansion of {{Pi}}, and ''f''(''n'') = 0 otherwise, is computable. (The function ''f'' is either the constant 1 function, which is computable, or else there is a ''k'' such that ''f''(''n'') = 1 if ''n'' < ''k'' and ''f''(''n'') = 0 if ''n'' ≥ ''k''. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know ''which'' of those functions is ''f''. Nevertheless, we know that the function ''f'' must be computable.)
* Each finite segment of an ''un''computable sequence of natural numbers (such as the [[Busy beaver#Score function Σ|Busy Beaver function]] Σ) is computable. E.g., for each natural number ''n'', there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(''n'') — in contrast to the fact that there is no algorithm that computes the ''entire'' Σ-sequence, i.e. Σ(''n'') for all ''n''. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of ''n'', such a trivial algorithm ''exists'' (even though it may never be ''known'' or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(''n'').