A total function for which there is an effective method of computing its output, for every input.

A computable function can also be defined as one that can be computed by an algorithm, or (equivalently), by a Turing Machine. For example:

f(n) = n + 1 is a computable function. The algorithm that solves it takes the input and adds one. (How simple is that?)

Turing's Halting Problem is an incomputable function.

Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.