Recursive Language

languages

Definition

Recursive Language

A language $\mathcal{L}\subseteq {\Sigma }^{\ast }$ is recursive (or decidable) if there exists a total Turing machine $M$ such that, for every input $w\in {\Sigma }^{\ast }$, $M$ halts and:

1. if $w\in \mathcal{L}$, $M$ accepts $w$;
2. if $w\notin \mathcal{L}$, $M$ rejects $w$.

Equivalently:

• The characteristic function ${\chi }_{\mathcal{L}}:{\Sigma }^{\ast }\to \{0,1\}$ is computable.
• Both $\mathcal{L}$ and its complement $\overline{\mathcal{L}}$ are recursively enumerable.
• There exists a program that, given any string $w$, decides membership in finite time.

Equivalence with Decision Problem

Decision Problem $⟺$ Recursive Language

Let a decision problem $\mathcal{P}$ have instances in some set $D$ and “yes”-instances $Y\subseteq D$.

Fix a computable encoding $\mathrm{enc}:D\to {\Sigma }^{\ast }$. Define the language of the problem:

$$L_{\mathcal{P}}=\{\mathrm{enc}(y)\mid y\in Y\}\subseteq {\Sigma }^{\ast }$$

Then:

$$\mathcal{P}\text{ is decidable}⟺L_{\mathcal{P}}\text{ is recursive (decidable) language}$$

Decision Problem $⟺$ Recursive Language

$(⟹)$: If $\mathcal{P}$ has a decider $A$, build a Turing machine $D$ that on input $w$:

$D$: decode $w$ to $x$; if decoding fails, reject; else run $A(x)$ and accept iff “yes”.

$(\Leftarrow )$: If $L_{\mathcal{P}}$ has a decider $D$, then the algorithm for $\mathcal{P}$ is:

$D$: on instance $x$, run $D$ on $\mathrm{enc}(x)$ and answer “yes” iff $D$ accepts.