How to prove that a set is recursively enumerable?

47 Views Asked by At

I was preparing for my "Theoretical Computer Science" exam and, while reviewing some old tests, I came across an exercise about recursively enumerable sets. My intuition was to try to exploit the property that says that the composition of partially computable functions is partially computable but couldn't figure out how to make it work in this case. What am I missing?

Here's the exercise: Having a computable function $h(x)$ and a set $C = \{ x \space | \space h(x) \in D \}$, how would you prove that $C$ is recursively enumerable knowing that $D$ is recursively enumerable?

1

There are 1 best solutions below

1
On BEST ANSWER

Let $f$ be a partial computable function witnessing $D$'s recursive enumerability. Then $f\circ h$ is a partial computable function witnessing $C$'s recursive enumerability.