Proving that sets are recursive

Question

I am stuck on proving that given sets are recursive or recursively enumerable. Those sets are:

$$\begin{align} f(A) &= \{y, \exists x \in A:f(x) = y\}\\ f^{-1}(A) &= \{x, f(x) \in A\} \end{align}$$

where $A$ is a recursive set and $f : \mathbb N \to \mathbb N$ is a computable function.

I am new to computability theory so any advice that is understandable for a newbie would be highly appreciated.

Answer 1

I will use the terminology "recursively enumerable" and "recursive" (= "decidable").

A set $X$ is recursively enumerable iff. there is an algorithm, which started with a word $w \in X$ halts in an accepting state, and which started with a word $w \notin X$ either does not halt or halts in a non-accepting state. Depending on your flavor of computation, you could specify the algorithm in natural language or in a tedious write-up of a Turing machine or combinations.
Note that whenever I use the word "algorithm" I imply the existence of Turing machine exactly implementing that behavior. As you may know there are many computational models — Turing machines and $\lambda$ calculus being the well-known ones.

Let $A \subseteq \mathbb{N}$ be a decidable set and $f: \mathbb{N} \to \mathbb{N}$ a computable function.

Consider your first problem:

$$f(A) = \{y\ |\ \exists x \in A:f(x) = y\}$$ You need to give an algorithm which should halt on an input $y$ for which we have $\exists x\in A: f(x) = y$. For other inputs the algorithm may not halt at all or halt non-acceptingly.
If I gave you such an arbitrary $y \in \mathbb{N}$, how would you go about determining $y \in f(A)$? Surely, you would try out all $x \in A$ and verify whether $f(x) = y$. And that's the algorithm:

1. Read input $y \in \mathbb{N}$
2. For all $x \in A$:
   1. Compute $f(x)$.
   2. Test whether $f(x) = y$
   3. If so, then halt acceptingly.
   4. Otherwise continue.

Since we did not give a specific Turing machine (that 7-tuple with states, band alphabet, ... if you remember), but a natural language algorithm. This requires careful observation of the validity of all steps. Are all steps really implementable by a Turing machine, by a human given enough time so to say.

Hence stop for a moment and think why the steps 2 and 2.1 are actually valid. Then also try answering if the whole block 2 ever terminates.

---

Validity of step 2

Any recursively enumerable set effectively enables the usage of a "for all/each" loop, where the loop terminates iff. the set was finite. Hence, any decidable set has the same property. This can be seen by defining the for all loop in the following way:

For a recursively enumerable set $X$ define "for all $x \in X$" as the following (sub-)algorithm/subroutine:

$X$ was recursively enumerable, hence a Turing machine $M''$ exists, which halts acceptingly on inputs from $X$. 1. For all $n \in \mathbb{N}$ (or your favorite "base encoding", e.g. $\{0, 1\}$): 1. Start $M''$ with input $n$ and only perform one step. 2. Continue exactly one step in all previously started Turing machines. 3. If any of those machines halted acceptingly, then do ??? (where ??? is determined by the algorithm using this subroutine) 4. Continue

---

Validity of step 2.1

$f$ is a computable function, hence there is a Turing machine $M'$ which given an input $n \in \mathbb{N}$ halts in an accepting state with output $f(n)$.

Thoughts on termination

By definition of step 2, the algorithm never terminates for inputs not in $f(A)$. This is not necessary for $f(A)$ to be recursively enumerable. In fact, we could even halt for values outside of $f(A)$ - but notably non-acceptingly in that case!

Correctness of algorithm

Let $M$ denote a Turing machine implementing the main algorithm above. Try proving $L(M) = f(A)$ by proving $L(M) \subseteq f(A)$ and $f(A) \subseteq L(M)$. This may or not may be obvious to you. This requirement corresponds to the wording above:

A set $X$ is recursively enumerable iff. there is an algorithm, which started with a word $w \in X$ halts in an accepting state, and which started with a word $w \notin X$ either does not halt or halts in a non-accepting state.

Now you proved that $f(A)$ is recursively enumerable! Further food for thought: Could $f(A)$ be even decidable? Answer:

Not in general, but consider $A$ being the recursively enumerable set $H$ of all halting Turing machines and $f \equiv 1$ — a constant function. Surely, $f(A)$ is decidable: if the input is $1$, then accept it, otherwise don't accept it.

If $A$ is decidable, is then $f(A)$ decidable as well? Answer:

No in general, you still have to search through the whole set $A \subseteq \mathbb{N}$ to look for the preimage of $y$. In other words, step 2 is still a non-halting subroutine.

How could you prove this formally?

Choose $A = \mathbb{N}$, $f: A \to \mathbb{N}$ so that it enumerates $H$. Note that $f$ is computable with $f(A) = H$. Decidability of $f(A)$ would contradict the well-known undecidability of $H$.