Explaining the difference between two definitions for recursively enumerable languages.

Question

I'm a little confused about the definition for recursively enumerable languages in my script. A recursively enumerable language is defined as:

A language $A \subseteq \Sigma^*$ is called recursively enumerable, if $A = \emptyset$ or there exists a total and computable function $f: \mathbb{N} \to \Sigma^*$ with $A=\{f(0), f(1), f(2), ...\} := f(\mathbb{N})$. Then $f$ enumerates $A$.

However, the definitions that I found on Wikipedia and Youtube videos is rather different. For example, according to Wikipedia:

A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language.

The second definition makes more intuitive sense to me and also seems more widely accepted. What's the connection between the two definitions? From what I understand, the first definition essentially "numbers" each alphabet in $A$. But I'm not sure.

Answer 1

Call the first concept enumerable and the second one semi-decidable. You want to show that $A\subseteq\Sigma^*$ is enumerable if and only if $A$ is semidecidable.

Assume first that $A$ is enumerable; we have to find a Turing machine which matches the "semi-decidable" description (this is the simple direction). If $A=\emptyset$, take the machine which always rejects. If $A\neq\emptyset$, consider the machine which does the following: Given an input $x$, start computing $f(0),f(1),f(2),\ldots$ If you encounter an $i$ such that $f(i)=x$, then accept. Note that the computation will never halt if $x\notin A$.

Assume now that $A$ is semidecidable, as witnessed by some Turing machine $T$. We want to find a computable function $f$ enumerating $A$. If $A$ is finite, you can simply write down a (non-injective) enumeration function, so assume $A$ is infinite. Let $x_1,x_2,\ldots$ be an enumeration of $\Sigma^*$, and let $n$ be the input for the function we are going to define. $f(n)$ is computed as follows: Using the machine $T$, perform one computation step on $x_1$. Then perform a second computation step on $x_1$ and a first computation step on $x_2$. Then do a third computation step on $x_1$, a second computation step on $x_1$ and a first computation step on $x_3$. Continue in this fashion, so that you are computing in parallel more and more steps on more and more inputs. When you get an "accept" answer on some input, do not continue the computation on that input. Wait until you get the $(n+1)$-th "accept", say on input $x_i$. Then output $f(n):=x_i$. (Note that since $A$ is infinite, you must eventually get an $(n+1)$-th accept, so the computation of $f$ on $n$ terminates.)