Multicombinators as observable presheaves

Abstract

In this paper we introduce the concept of multicombinators as an alternative Turing-complete model of computation, modallyextending the formalism of Combinatory Logic. We present a diagrammatic representation of multicombinators as presheavesdefined over a category of generic figures. By adopting Sergeyev’s grossone numeral system, we obtain a sharper characterization of non-halting multicombinators. As a result of our analysis, we show how results for “infinite” combinators using thegrossone formalism involving the notion of observability may be extended to the setting of multicombinators. These resultsformalize the general concept of tractable properties of multicombinators involving sequences of length less than or equal togrossone.