On the existence of n but not n + 1 easy combinators

摘要

Recall that M is easy if it is consistent with every combinator. We say that M is m-easy if there is no proof with < m + 1 steps that M is inconsistent with any combinator. Obviously, if M is easy, it is m-easy for each m. Here we shall show that for infinitely many m there are m but not m + 1 easy terms.