Intensional Language Property

languages

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.

Examples

Intensional Language Property

• Syntactic constraints: “$M$ has $\le k$ states”, “uses symbol #”, “is $2$-tape”.

• Operational constraints not fixed by the language: “$M$ halts on every input”, “$M$ runs in $\le n$ steps on inputs of length $n$”.

• The given Turing machine for $L$ has $\le 7$ states / uses alphabet symbol #.

• The input $\epsilon$, the recognisers touches $>100$ tape cells.

• This NFA for $L$ is deterministic.