Metric Iteration Theories
Douglas R. Troeger · Fundamenta Informaticae · 1982
It is known that it is possible to impose a metric on the free iteration theory Γtr of Γ-trees such that the iterate f† of any tree f : n → p + n is a limit of of ‘finite approximations’ of f. Since this notion of limiting computation corresponds to our intuitive notion of iteration, it is natural to ask which other theories in the variety generated by Γtr admit such a metric. An algebraic characterization of these theories is presented In this paper.