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

Function	Intuitive meaning	Definition
Primitive recursive function		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)		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.

What if we try to define a characteristic function for a semirecursive relation $S$ as follows?

${\chi }_S(x,y)=\{\begin{array}{cc}1& S(x,y)\\ 0& \mathrm{\neg }S(x,y)\end{array}$

Actually we should distinguish between different levels of badness of ${\chi }_S$, and ask separately if it is well-defined, total, and recursive.

Since $S$ is semirecursive, there is some recursive relation $R$ such that $S(x,y)⟺\mathrm{\exists }t(R(x,y,t))$. And since $R$ is recursive, it has a recursive total characteristic function ${\chi }_R$. Our goal, then is to try to define ${\chi }_S$ in terms of ${\chi }_R$.

$g(x,y)=\mu t[{\chi }_{\mathrm{\neg }R}(x,y,t)=0](x,y)$

The problem is that $g$ is only a semicharacteristic function. And it seems there is no way to get a characteristic function for $S$ using the processes for defining recursive functions.