Recursive Languages

Procedure

A finite sequence of instructions that can be mechanically carried out, given any input.

Algorithm

A procedure that terminates after a finite number of steps for any input.

Recursively-enumerable

Enumerable means, all elements of a set or a language can be list in an order.

A set $X$ is recursively-enumerable iff there exists a procedure to determine whether an element $x$ belongs to the set or not.

A language $L$ is recursively-enumerable (aka. Turing-acceptable) iff there exists a Turing machine that accepts $L$.

A $k$-tape Turing machine $T$ is said to enumerate a language $L \subseteq \Sigma^*$ iff:

• Tape head on 1st tape:
  • never moves to left
  • no non-blank symbols on it
  • never modified layer
• For every string $x \in L$, at some point 1st tape will contain $x_1\#x_2\#\dots\#x_n\#x\#$ for some $x\ge 0$ where the strings $x_1,x_2,\dots,x_n,x$ are distinct elements of $L$
• If $L$ is finite, nothing is printed after # following the last

If $L_1$ and $L_2$ are recursively-enumerable languages, then $L_1 \cup L_2$ and $L_1 \cap L_2$ are also recursively-enumerable.

Recursive

A set $X$ is recursive iff there exists an algorithm to determine whether a given element belongs to $X$ or not.

A language $L$ is recursive (aka. Turing-decidable or decidable) iff there exists a Turing machine that decides $L$.

A language $L$ is recursive iff there exists a Turing machine that enumerates $L$ in canonical order (i.e. shorter strings come first and in lexicographical order).

If $L$ is recursive, $L' = \Sigma^* - L$ is also recursive.