Expressive power of typed and type-free programming languages (Q761790)

The paper investigates the influence of type-free programming concepts on the definability of functions and objects in comparison with the exclusive use of typed concepts plus fixed-point operators. The underlying schemes are the classes of type-free and typed lambda-schemes respectively. The formal semantics of both classes are analyzed in the same semantical domains. In particular it is shown that typed lambda- schemes are translatable into equivalent type-free lambda-schemes but not vice verse. Furthermore, it is proved that the class of type-free lambda- schemes is universal in the sense that in the initial models all recursively enumerable \(\Sigma\)-trees (where \(\Sigma\) is the set of operation symbols) are definable.