Andrew Polonsky - Fixed point combinators as fixed points of higher-order fixed point generators

lmcs:4872 - Logical Methods in Computer Science, July 23, 2020, Volume 16, Issue 3 - https://doi.org/10.23638/LMCS-16(3:7)2020
Fixed point combinators as fixed points of higher-order fixed point generatorsArticle

Authors: Andrew Polonsky

    Corrado Böhm once observed that if $Y$ is any fixed point combinator (fpc), then $Y(\lambda yx.x(yx))$ is again fpc. He thus discovered the first "fpc generating scheme" -- a generic way to build new fpcs from old. Continuing this idea, define an $\textit{fpc generator}$ to be any sequence of terms $G_1,\dots,G_n$ such that \[ Y \in FPC \Rightarrow Y G_1 \cdots G_n \in FPC \] In this contribution, we take first steps in studying the structure of (weak) fpc generators. We isolate several robust classes of such generators, by examining their elementary properties like injectivity and (weak) constancy. We provide sufficient conditions for existence of fixed points of a given generator $(G_1,\cdots,G_n)$: an fpc $Y$ such that $Y = Y G_1 \cdots G_n$. We conjecture that weak constancy is a necessary condition for existence of such (higher-order) fixed points. This statement generalizes Statman's conjecture on non-existence of "double fpcs": fixed points of the generator $(G) = (\lambda yx.x(yx))$ discovered by Böhm. Finally, we define and make a few observations about the monoid of (weak) fpc generators. This enables us to formulate new a conjecture about their structure.


    Volume: Volume 16, Issue 3
    Published on: July 23, 2020
    Accepted on: June 19, 2020
    Submitted on: October 5, 2018
    Keywords: Computer Science - Logic in Computer Science,03B40,F.4.1

    Consultation statistics

    This page has been seen 1653 times.
    This article's PDF has been downloaded 533 times.