Extensional PERs (Q1193589)

Mathematical (denotational) semantics of programming languages requires a general framework supporting computational models and effectiveness. Searching for a good category of domains, the authors present results on a class of Partial Equivalence Relations (PERs) on natural numbers. Extensional PER (ExPER for short) is a Cartesian closed category where every endomorphism has a canonical fixed point. Domain equations are guaranteed to have solutions because all basic functors are realizable and have canonical invariant objects. The notions which appear in the paper related to the category (Ex)PER are defined using familiar tools from computation theory, namely Turing machines.