1
$\begingroup$

I want to show the following two propositions:

  • The domain of a recursive function is recursively enumerable.
  • The range of a recursive function is recursively enumerable.

I have thought the following in order to prove the first proposition.

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$. So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes". Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

Is my idea right? If so, can't we also deduce from that that the domain of a recursive function is recursive since the algorithm always terminates for the elements of the domain?

Can you give me a hint how we can show the second proposition?

$\endgroup$
2
$\begingroup$

The first proof looks ok. (Actually, it depends on the definition you use for RE. Some authors define RE iff it's the domain of a recursive function, making the exercise trivial.)

For the second, here's a hint. Given $x$ you want to check whether $f(0)=x$ or $f(1)=x$ or ... If all of these are false, we can diverge (we must diverge, actually), but if any of these is true, we must halt. We can not proceed with a simple infinite iteration, since $f(1)$ might diverge and $f(2)$ might return $x$, and if so we need to detect that and halt anyway.

So, we need to evaluate in parallel all these programs, so that even if one of them diverges does not stop the evaluation of the others.

Think of a fair scheduler among infinitely many processes. Think about running a program for only a given number of steps. Think about doves and their tails. ;-)

$\endgroup$
  • $\begingroup$ I am using this definition: A subset $A$ of $\mathbb{N}^k$ is RE iff there is a turing machine $M$ such that for $x \in A$, $M$ with input $x$ halts, giving output $1$ and for $x \notin A$ , $M$ does not halt. So do we deduce that the domain of a recursive function is recursive? $\endgroup$ – Evinda Feb 1 '17 at 11:41
  • $\begingroup$ So, for the second question: Let $x \in range (f)$, where $f$ is a recursive function. Suppose that we have so many tapes, as the number of elements of the domain. Since $f$ is recursive, there is a Turing machine $M$ that computes it. We run simultaneously $M$ on the different elements of the domain at the tapes. If $M$ halts at some tape, the Turing machine should halt on $x$, otherwise it should not. Right? $\endgroup$ – Evinda Feb 1 '17 at 11:42
  • $\begingroup$ @Evinda You can't add infinitely many tapes, that is too much. It would enable a TM to compute any arbitrary function. But you can keep $k$ representation of tapes on a single tape, and increment $k$ every so often. In such way, at any given time you only use a finite amount of memory, but eventually $k$ will be large enough to run every TM you want to simulate. $\endgroup$ – chi Feb 1 '17 at 12:00
  • $\begingroup$ @Evinda We don't deduce the domain is R but is RE. The proof is what you wrote in the question, except that you need to ensure the output is $1$ to comply with the definition. Just compute $f(n)\cdot 0 + 1$, which is recursive as well and has the right domain and output. $\endgroup$ – chi Feb 1 '17 at 12:02
  • $\begingroup$ If we have a single tape that constains $k$ tapes, how can we run simultaneously the machine at each tape? $$$$ Can we say that $A$ with an input that does not belong in the domain of $f$ gives output $\infty$ ? $\endgroup$ – Evinda Feb 1 '17 at 13:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.