Submitted by Corrado Böhm
Statement. On the equational meaning of deeds
Problem Origin. The problem has been posed ﬁrst by Corrado Böhm . It is added to the list to celebrate his 90th birthday.
A deed is a closed normal form with only one initial abstraction, namely a deed has shape where .
It is easy to verify that each equation of the shape
where , are deeds, can be solved, for instance by choosing a ﬁxed point of the combinator as .
It it possible to deﬁne a one-one mapping between arbitrary normal forms and deeds, as follows. Given a normal form with initial abstractions, the deed corresponding to is:
The question is as follows: What can we understand about the solution of the equation , where are arbitrary normal forms, by looking at the equation ?