Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Recursion

Aliases: Recursive Function

Keywords: Turing machine

Categories: Inference and Reasoning , Knowledge Representation , Theorem Proving

Author(s): Fausto Giunchiglia

Recursion theory has been developed by logicians (mainly K. Gödel and S.C. Kleene) in the 1930's as a way to formalise metamathematics. Recursive functions can be given by definitions involving reference to the function being defined. For instance:

if    then else

where is a natural number, is the recursive definition of the factorial. Since recursive functions are all and only the functions computable by idealised computers (Turing machines), recursion theory has been extended to domains different from the natural numbers (e.g., lists) and used by computer scientists as a powerful tool to reason about programs. Applications include the theory of computation, complexity of programs, program synthesis and program verification.

References:

Comments:
Add Comment

No comments.