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.

  • 1
    $\begingroup$ The two definitions are equivalent. $\endgroup$ Jan 15, 2021 at 22:15
  • $\begingroup$ @BrianM.Scott Could you please explain the first definition and how it relates to the second one? $\endgroup$
    – Ski Mask
    Jan 15, 2021 at 22:20
  • $\begingroup$ The first definition says that if $A$ is non-empty, there is a computable, total function that enumerates $A$. If $A$ is finite the enumeration will obviously have repetitions, but if $A$ is infinite, the function can always be chosen to be a bijection. The two definitions are simply expressed in terms of two superficially different but provably equivalent notions of computable function. $\endgroup$ Jan 15, 2021 at 22:24

1 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.)

  • $\begingroup$ And what exactly are $f(0), f(1), ...$ here? $\endgroup$
    – Ski Mask
    Jan 16, 2021 at 9:25
  • $\begingroup$ $f$ is the function which witnesses that $A$ is enumerable - I forgot to mention. $\endgroup$
    – Timo
    Jan 16, 2021 at 10:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .