Science Fair Project Encyclopedia
In computability theory computable functions or Turing computable functions are the basic objects of study. They make our intuitive notion of algorithm precise and according to the Church-Turing thesis they are exactly the functions that can be calculated using a mechanic calculation device.
Before the precise definition of computable function mathematicians often used the informal term effectively computable.
Generally a computable function is a partial function
The class of computable functions is equivalent to the class of functions defined by
Alternatively they can be defined as those algorithms that can be calculated by
Sometimes, for reasons of clarity, we write a computable function as
We can easily encode g into a new function
using a pairing function.
- constant function f : Nk→ N, f(n1,...nk) := n
- addition f : N2→ N, f(n1,n2) := n1 + n2
- greatest common divisor
- Bézout's identity, a linear Diophantine equation
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details