Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T12:18:46.222Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  01 August 1999

RICK STATMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© 1999 Cambridge University Press