Fixed Point Equations Inside the Algebra of Normal Forms

Article type: Research Article

Authors: Böhm, Corrado

Affiliations: Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza” Rome, Italy. email: boehm@dsi.uniromal.it

Note: [] Address for correspondence: Dipartimento di Scienze dell'Informazione, Università di Roma “La Sapienza”, Rome, Italy

Abstract: Solutions of the equations X = ZX and X = XZ are found and discussed for Z, X normal terms of the lambda-calculus. Obviously fixed point combinators are of no help. Solutions will be independent from any kind of gödelization or coding of data structures, they will be provided by typeless self-application. Different approaches will be shown: algebraic properties, one side invertibility and idempotency. Certain subsets of proper combinators and Church algebras between them will be proved to be domains consisting only of fixed points of combinators.

Keywords: Lambda Calculus, Abstract Algebras, Fixed Point Equations

DOI: 10.3233/FI-1999-37401

Journal: Fundamenta Informaticae, vol. 37, no. 4, pp. 329-342, 1999