I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable.

  1. the set $A = \{ i | \text{Dom}(\phi_i) = \emptyset \}$, where $\text{Dom}(\phi_k) = \{x | \phi_k(x) \downarrow \}$, and where $\phi_k(x) \downarrow$ means that function with index $k$ converges at input $x$.

  2. the set $B$ of all total recursive functions $a : \mathbb{N} \rightarrow \mathbb{N}$ such that $a(n+1) \geq a(n)$, for all $n \in \mathbb{N}$

Please note that I have this definition for recursive sets, and this definition for recursive enumerable sets (r.e.). I also know that, if a set $A$ is recursive, then $A$ is also r.e.

The problem is that, I don't know how to argue about whether the sets above are recursive, r.e., or none of them. Any ideas about the problems?


$$\text{Halt}(x,y) = \begin{cases} 1, & \mbox{if } \phi_x(y) \downarrow \\ 0, & \mbox{if } \phi_x(y) \uparrow \end{cases}$$

where $\phi_x(y) \downarrow$, means function with index $x$ converges on input $y$, and $\phi_x(y) \uparrow$ means that it diverges.

  • $\begingroup$ Do you know about reductions? One way to prove that something is not recursive is to use non-recursiveness of some fixed set (e.g. the halting problem) and reduce it to your set. $\endgroup$ – Random Jack Jan 3 '16 at 21:29
  • $\begingroup$ @RandomJack Yes, I know about reductions, but it never occurred to me that it can be used to solve this kind of problems, I though, I only need the definitions. I believe I can define the halting problem as in my edit. But, how will the reduction look like. And by your definition, if I manage to reduce the sets to Halting problem, then it means that they are neither recursive nor r.e., right? $\endgroup$ – user72151 Jan 3 '16 at 21:40

Let $K$ be the halting problem set $\{x \in \mathbb{N} \mid \phi_x(x) \downarrow\}$. It is known that $K$ is not recursive and hence (by Post's theorem) its complement $\overline{K}$ is not r.e. We say that $X$ is m-reducible to $Y$ (notation: $X \leq_\text{m} Y$) if there is a total recursive function $f(x)$ with $x \in X \Leftrightarrow f(x) \in Y$. It is quite easy to show that if $X \leq_\text{m} Y$ and $Y$ is recursive (r.e.), so is $X$.

To show that $A$ is not r.e. (and hence is not recursive) we will show that $\overline{K} \leq_\text{m} A$. Consider the following function $$f(x, y) = \begin{cases} 1,& x \in K\\ \uparrow,& x \notin K \end{cases}$$

It is partial recursive and by the $s_m^n$-theorem there is a total recursive $g(x)$ with $\phi_{g(x)}(y) = f(x, y)$. It holds that $$x \notin K \Leftrightarrow (\forall y) \phi_{g(x)}(y) = f(x, y) =\,\uparrow\, \Leftrightarrow g(x) \in A.$$

Now assume that $B$ is r.e. and let $U(n, x) = a_n(x)$ be a total recursive universal function for this set, that is, the functions from $B$ form a sequence $U(0, x), U(1, x), \dots$. Consider the following function: $$g(n) = \sum_{i = 0}^n U(i, n) + 1.$$ It is clearly a total recursive function. Since $U(i, n+1) \geq U(i, n)$ it holds that $$g(n+1) = \sum_{i = 0}^n U(i, n+1) + U(n+1, n+1) + 1 \geq \sum_{i = 0}^n U(i, n) + 1 = g(n),$$ hence $g(n) \in B$. On the other hand, if for some $m$ we have $U(m, n) = g(n)$, then taking $n = m$ we obtain $$U(m, m) = \sum_{i=0}^m U(i, m) + 1,$$ which is false. It means that $g(n) \notin B$, a contradiction. Hence $B$ is not r.e. (and, of course, is not recursive).

| cite | improve this answer | |
  • $\begingroup$ So, as long as I understood, you assert that both set $A$ and $B$, are neither recursive nor r.e., am I right? On the other hand, what do you mean with "$m$-reducible"? What's the significance of $m$? $\endgroup$ – user72151 Jan 4 '16 at 13:47
  • 1
    $\begingroup$ Yes, both these sets are neither recursive nor r.e. For the set $A$ I use reduction of some fixed non-r.e. set (namely, the complement of $K$) to $A$, and for $B$ I prove it directly by constructing a function $g(n)$ (using diagonalization ideas) that leads to a contradiction. There are many different notions of reducibility (many-one, one-one, Turing, truth table and others), the letter 'm' stands for 'many-one'. $\endgroup$ – Random Jack Jan 4 '16 at 21:19
  • 1
    $\begingroup$ Got it, thanks! $\endgroup$ – user72151 Jan 4 '16 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy