0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.