I have been asked to prove that:

Being C an infinite set. Prove that C is semidecidable if and only if exists a total computable function that is injective and whose image is C.

I've read the wikipedia articles of computable function and recursively enumerable set and I saw these properties are true. But I have no idea how to start the proof.

Could you please help me?

Thanks in advance.


Here is a rough sketch.

If $M$ recognizes $C$, we can exploit $M$ to craft $N$ which enumerates the language of $M$, writing all its words on an output tape, clearly separated, in infinite time. For that, it suffices to exploit dovetailing to generate all the pairs $(w,k)$, where $w$ is a word and $k$ a natural. For each such pair, we run $M$ on $w$ for $k$ steps -- if $M$ accepts, we add $w$ to the output tape, otherwise we try the next pair.

Exploiting $N$ is then possible to define a total computable $f$ whose image is $C$.

For the other direction, given a total computable $f$, we can craft $M$ such that on input $w$ compares it to $f(0),f(1),f(2),\ldots$. In this way we can make $M$ recognize the image of $f$, i.e. $C$.

| cite | improve this answer | |

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.