[Next]  [Previous]  [Up]

#### Problem # 24

Submitted by Corrado Böhm
Date: 2013
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.

[PRINT this PROBLEM]

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: where are the Church numerals or any distinct closed beta-eta normal forms. Note that the mapping is injective by Böhm’s theorem.

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 ?

##### References for # 24

[Next]  [Previous]  [Up]
Last modified: July 21, 2014