Computable and partial recursive functions

A function f from words to words (over a finite alphabet) is called computable if there exists an method - any method at all - to compute it. It is recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts every input, and when given input string x, leaves the string f(x) on its tape upon acceptance.

A partial function is called partial recursive if it can be computed by a Turing machine; that is, if there exists a Turing machine that accepts input x exactly when f(x) is defined, in which case it leaves the string f(x) on its tape upon acceptance.

By Church's thesis, a function is recursive if and only if it is computable.


Rob van Glabbeek rvg@cs.stanford.edu