Stone: Section 15
From CSWiki
Contents |
Recursive Theory and Recursively Enumerable Sets
Key Points
- A function must be total and partial recursive to be recursive.
- All primitive recursive functions are recursive.
- Every finite set of natural numbers is recursive.
- The characteristic function of a recursive set is a predicate that accepts all members of that set.
- A set is recursively enumerable iff there is a singulary partial recursive function which is defined for the inputs which are exactly the members of that set. This function f is called the acceptance function for S.
- Recursive sets are a proper subset of recursively enumerable sets.
Definitions
- A set, S, is a recursive set iff there is some total, singulary, partial recursive function, p, such that
. In simpler terms, if a set is the input upon which some singulary recursive function will return true, that set is recursive. Hence {0,2,4,6,8,...} is recursive as "even?" exists.
Theorems
Theorem 15.1
The set of encodings of valid computations is recursive.
This is proved by the existence of computation?, which is primitive recursive.
Theorem 15.2
K is not recursive.
K is the set of encodings of pairs where the first member is an encoding for a partial recursive function and the second member is the encoding for a list of inputs for that function.
Theorem 15.3
The union 
and the intersection of any recursive S and T are recursive.
Union can be defined with the primitive-recusrive function or, intersection with the primitive recursive and.
Theorem 15.4
The complement of any recursive set is recursive.
The complement of a recursive set can be defined with the primitive recursive not function.
Theorem 15.5
Every recursive set is recursively enumerable.
The characteristic function of a recursive set is the acceptance function for that set.
