Definition
Intensional Function Property
Fix a representation of computable functions (e.g. Turing machines). A function property is intensional if it is a predicate on machine encodings
that is not invariant under extensional equality of the computed function.
Equivalently, there exists
with the same computed function but .
depends on how the function is implemented, not only on the input-output mapping.
Examples
Intensional Function Property
- The machine halts in
steps on every input. - The program has
states / contains instruction . - On empty input, the machine writes on
cells. - The implementation is written as primitive-recursive expression