User:IssaRice/Computability and logic/Comparison of concepts in computability theory

Function	Intuitive meaning	Definition
Primitive recursive function	Function can be computed using a bounded for-loop (i.e. a for-loop that is bounded and where the looping variable is not modified in the body of the loop)	Can be obtained from the basic functions (zero, successor, identity/projection functions) using a finite number of applications of composition and primitive recursion.
Partial recursive function (recursive total or partial function)	Function can be computed using a while-loop or an unbounded for-loop	Can be obtained from the basic functions (zero, successor, identity/projection functions) using a finite number of applications of composition, primitive recursion, and minimization (search operator).
Recursive function (recursive total function)		Can be obtained from the basic functions (zero, successor, identity/projection functions) using a finite number of applications of composition, primitive recursion, and minimization (search operator), and the partial function is total.

Set	Intuitive meaning	In terms of characteristic function	Notes
Primitive recursive set		The characteristic function (which must be a total function) is primitive recursive
Recursive set	Given any natural number, after a finite amount of time one can tell whether the number is in the set or not	The characteristic function (which must be a total function) is recursive
Semirecursive set	Given any natural number, if it is in the set, then after a finite amount of time one can tell that the number is in the set. If the number is not in the set, one never finds out.	The positive semicharacteristic function (which equals 1 if the given argument is in the set, and is undefined otherwise) is partial recursive.
Recursively enumerable set			This is the same as a semirecursive set.