CSC 341: April 11, 2007

From CSWiki

Instructor's notes for the class session

A set is recursive if, and only if, its characteristic function is partial recursive. A set is recursively enumerable if, and only if, there is a singulary, partial recursive function that is defined when given any member of the set as input and undefined when given a non-member.

All recursive sets are recursively enumerable, but not all recursively enumerable sets are recursive. A recursively enumerable set is recursive if, and only if, its complement is recursively enumerable.

The set of recursive sets is closed under union, intersection, and complementation. The set of recursively enumerable sets is closed under union and intersection, but not complementation.

A non-empty set is recursively enumerable if, and only if, it is the set of outputs of some singulary partial recursive function. This is the basis for the name: The partial recursive function is thought of as enumerating its outputs by mapping natural numbers to them.

In-class exercise: Prove that, for any singulary, total, partial recursive function $f$ that is strictly increasing (so that $f (n + 1) > f (n)$ for every natural number $n$ ), the set of outputs of $f$ is recursive.

In-class exercise: Prove that any set that is infinite and recursively enumerable has a subset that is infinite and recursive.

[edit]

Study questions

Is the set $\{1, 2, 4, 8, \ldots\}$ of powers of 2 recursive?
Describe the characteristic function of the set of powers of 2.
Describe the set whose acceptance function is $\texttt{[}\mu_1 \texttt{\ apply]}$ .
Let $p$ be any partial recursive predicate, let $n$ be the valence of $p$ , and let $S$ be the set of encodings of $n$ -element lists $(x_0, \ldots, x_{n - 1})$ such that $p(x_0, \ldots, x_{n - 1}) = 1$ . Show that $S$ is recursive.