zbMATH — the first resource for mathematics

A conjecture on numeral systems. (English) Zbl 0918.03009
A numeral system is defined, in this paper, as any infinite sequence of different, closed normal \(\lambda\)-terms. These can then encode the integers in \(\lambda\)-calculus. Barendregt has shown that if, for a numeral system, the successor, predecessor and zero test functions can be represented then so can all total recursive functions.
In this interesting paper the author shows that there are numeral systems with any two but not all three of these functions and conjectures that there are no two unary functions in terms of which all total recursive functions can be defined for an arbitrary numeral system.

03B40 Combinatory logic and lambda calculus
Full Text: DOI
[1] Barendregt, H., The Lambda Calculus, Its Syntax and Semantics , North-Holland, Amsterdam, 1984. · Zbl 0551.03007
[2] Krivine, J-L., Lambda Calcul, Types et Modèles Masson, Paris, 1990. · Zbl 0697.03004
[3] Krivine, J-L., “Opérateurs de mise en mémoire et traduction de Gödel,” Archive for Mathematical Logic , vol. 30 (1990), pp. 241–67. · Zbl 0712.03009 · doi:10.1007/BF01792986
[4] Nour, K., “An example of a nonadequate numeral system,” Comptes Rendus de l’Académie des Sciences, t. 323, Série 1 (1996), pp. 439–42.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.