Computable function

In computability theory 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 computed using a physical computing machine.

Definition

Many different ways can be used to define computable functions.

• recursive function
• Turing machine
• lambda calculus
• Markov algorithm
• Post system
• register machine