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)
that is not invariant under language equivalence.
Equivalently, there exists
with but .
depends on the particular machine/derivation for the language, not on the language itself.
Examples
Intensional Language Property
Syntactic constraints: “
has states”, “uses symbol #”, “is -tape”. Operational constraints not fixed by the language: “
halts on every input”, “ runs in steps on inputs of length ”. The given Turing machine for
has states / uses alphabet symbol #. The input
, the recognisers touches tape cells. This NFA for
is deterministic.