Recursively Enumerable Language

automata-theory languages

Definition

Recursively Enumerable Language

A language is recursively enumerable if there exists a Turing machine such that:

1. for every , halts and accepts ,
2. for every , either rejects or runs forever.

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

Equivalently, there’s a program that enumerates all strings of (possibly with repetition) , every member of appears after finite time.

Extensional

Definition

Extensional Language Property

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

Equivalently: if two Turing machines satisfy

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

Link to original

Trivial

Definition

Trivial Extensional

Fix an alphabet . An extensional family is called trivial if either or (all recursively enumerable languages over ).

Examples:

• (trivial)
• (trivial)

Link to original