Computable function

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. A broader class of functions, called A-computable, can be defined by extending Turing machines with an oracle for the set A.

Related Topics:
Computability theory - Algorithm - Church-Turing thesis - ''A''-computable - Oracle

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Before the precise definition of computable function mathematicians often used the informal term effectively computable.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Computable functions are used to discuss computability without referring to any concrete model of computation like turing machines or register machines. The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions.

Related Topics:
Model of computation - Blum axioms - Computational complexity theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

According to the Church-Turing thesis, the class of computable functions is equivalent to the class of functions defined by recursive functions, lambda calculus, or Markov algorithms.

Related Topics:
Church-Turing thesis - Recursive function - Lambda calculus - Markov algorithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Alternatively they can be defined as those algorithms that can be calculated by Turing machines, Post systems or register machines.

Related Topics:
Turing machine - Post system - Register machine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~