Effective operations on indices of r.e. sets
[9/67%]Assume that and . Show that if and are r.e., then .
Show that for every partial recursive function , there exists a recursive function such that .
Show that there is a recursive function such that for all ,
For any partial recursive function , we write to denote its domain . Let be three partial recursive functions.
Show that there exists a partial recursive function such that , and for each , or or .
Show that there does not always exist a partial recursive function such that , and for each or or , and for each .
Let be pairwise disjoint recursively enumerable sets of -tuples, partial recursive functions. Prove that , defined as follows:
is partial recursive.
Prove the recursive enumerability of the sets of all Kleene numbers of the following families of one-place partial recursive functions:
functions defined at the point ;
functions such that for given numbers and ;
functions with nonempty domain of definition.
Prove that the sets of all Post numbers of the following families of recursively enumerable sets are recursively enumerable:
those containing a given number ;
the nonempty ones.
Prove that for every recursively enumerable set () there is a primitive recursive function such that
Prove that there exist primitive recursive functions such that:
;
;
;
;
;
.
Prove that there exist primitive recursive functions and such that:
;
.