Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-28T22:01:54.631Z 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

Abstract

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.

Type
Research Article
Copyright
© 1999 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)