Language Property

languages

Definition

Language Property

Fix an alphabet $\Sigma$ and let $\mathcal{U}\subseteq \mathcal{P}({\Sigma }^{\ast })$ be a chosen universe of languages (typically $\mathcal{U}={\mathrm{RE}}_{\Sigma }$, the recursively enumerable languages for Rice’s theorem).

A language property is a is a predicate

$$P:\mathcal{U}\to \{\mathrm{true},\mathrm{false}\}$$

assigns true/false to entire languages $L\subseteq {\Sigma }^{\ast }$ (not to individuals words or to machine code).

Extensional vs. Intensional

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

Intensional

Definition

Intensional Function Property

Fix a representation of languages by machines (recognisers/deciders). A language property is intensionalif it is a predicate on recognisers (machine encodings)

$$R:\{⟨M⟩\}\to \{\mathrm{true},\mathrm{false}\}$$

that is not invariant under language equivalence.

Equivalently, there exists $M_1,M_2$ with $L(M_1)=L(M_2)$ but $R(⟨M_1⟩)\ne R(⟨M_2⟩)$.

$R$ depends on the particular machine/derivation for the language, not on the language itself.

Link to original

Decidability

Decidable

Definition

Decidable Language Property

A language property is decidable iff its code language is decidable.

Link to original

Undecidable

Definition

Undecidable Language

A language that is no decidable.

Link to original