Recursively Enumerable Language

automata-theory languages

Definition

Recursively Enumerable Language

A language $\mathcal{L}\subseteq {\Sigma }^{\ast }$ is recursively enumerable if there exists a Turing machine $M$ such that:

1. for every $w\in \mathcal{L}$, $M$ halts and accepts $w$,
2. for every $w\notin \mathcal{L}$, $M$ either rejects or runs forever.

i.e., there exists a Turing machine that accepts $L$.

Equivalently, there’s a program that enumerates all strings of $\mathcal{L}$ (possibly with repetition) $w_1,w_2,\dots$, every member of $\mathcal{L}$ appears after finite time.

Extensional

Definition

Extensional Language Property

A language property $P$ is extensional iff it depends only on the language itself.

Equivalently: if two Turing machines $M_1,M_2$ satisfy

$$L(M_1)=L(M_2)⟹P(L(M_1))=P(L(M_2))$$

This is the “semantics vs. syntax” separation used by Rice.

Link to original

Trivial

Definition

Trivial Extensional

Fix an alphabet $\Sigma$. An extensional family $\mathcal{E}\subseteq {\mathrm{RE}}_{\Sigma }$ is called trivial if either $\mathcal{E}=\varnothing$ or $\mathcal{E}={\mathrm{RE}}_{\Sigma }$ (all recursively enumerable languages over $\Sigma$).

Examples:

• ${\mathcal{E}}_1=\{L\mid L\text{ is semi-decidable}\}={\mathrm{RE}}_{\Sigma }$ (trivial)
• ${\mathcal{E}}_2=\varnothing$ (trivial)

Link to original