Write a procedure to demonstrate that $L$ is recursively enumerable.

Question

Let $L$ be a recursive language. Is $L$ recursively enumerable? If yes, write a procedure that demonstrate it. If not, write a counterexample.

Given that $L$ is recursive we know there exist an algorithm $A$ that for every $w \in \Sigma^*$ decide if it belongs to $L$ or not.

From that follows that $L$ is recursively enumerable because we can construct a procedure $P$ that simulates the algorithm $A$ on inputs $w \in L$ and whenever $A$ decide that $w$ is in $L$ then $P$ states it as well; on the other end, when $A$ decide that $w$ in not in $L$ then $P$ simply never terminates.

How would you construct a procedure (in pseudo code) to demonstrate this?

Answer 1

Details will, of course, depend on your conventions for pseudo-code, but I'd write something like the following (assuming $w$ is given to the algorithm as "input"):

if output(A(input))=yes then (print "yes"; halt)

else while $0=0$ do $x:=0$.