Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T07:51:16.674Z Has data issue: false hasContentIssue false

Taming the wild ant-lion; a counterexample to a conjecture of Böhm

Published online by Cambridge University Press:  07 August 2015

RICK STATMAN*
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A Email: statman@cs.cmu.edu
Rights & Permissions [Opens in a new window]

Extract

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.

In Barendregt (1984), Corrado Böhm conjectured that every adequate (Barendregt 1984, 6.4.2 (ii)) numeral system of normal combinators has normal successor, predecessor and zero test. In this note, we give a counterexample to this conjecture. Our example is shown to have no normal zero test. Böhm has informed us that Intrigila (1994) has given an example with no normal successor. Our strategy, in terms of the ant-lion paradigm, is to pry open the trap so wide that it enters its active state before its jaws are shut.