Set that is recursively enumerable but is NOT decidable

computabilitycomputational mathematics

I was trying to find a set that is recursively enumerable
i.e
$$
\exists f\; \text{computable and a program $P$ that computes}\; f
$$
such that
$$
A = \{ x\; :\; P(x)\downarrow \}.
$$

But it is not decidable so it's characteristic function is not computable.
I tried with using the Halting problem and taking $A$ as
$$
A = \{ x\; :\; \text{ the $x$-th computable function stops }\}
$$

but I don't think that A is recursively enumerable.
Thank you.

Best Answer

The set $S_h=\{ (x,y) | \text{program x halts when run on input y} \}$ is recursively enumerable since a universal program that takes input $(x,y)$ and emulates program $x$ running on input $y$ will halt for exactly the inputs in $S_h$. However, as the halting problem shows, $S_h$ is not decideable because its complement is not recursively enumerable.

Related Question