Combinators, as defined originally by Moses Schönfinkel, give rise to a Turing-complete model of computation. This paper presents a diagrammatic representation of combinators as presheaves defined over a category of generic figures. We adopt Sergeyev’s grossone numeral system, which, together with our categorical representation of combinators, ensures a sharper characterization of non-halting combinators. As a result of our analysis, we show how certain “infinite” combinators can be recast in the grossone formalism using the notion of observability, which captures the general concept of tractable properties of sequences with length less than or equal to grossone.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Combinators as Observable Presheaves: A Characterization in the Grossone Framework

  • Rocco Gangle,
  • Fernando Tohmé,
  • Gianluca Caterina

摘要

Combinators, as defined originally by Moses Schönfinkel, give rise to a Turing-complete model of computation. This paper presents a diagrammatic representation of combinators as presheaves defined over a category of generic figures. We adopt Sergeyev’s grossone numeral system, which, together with our categorical representation of combinators, ensures a sharper characterization of non-halting combinators. As a result of our analysis, we show how certain “infinite” combinators can be recast in the grossone formalism using the notion of observability, which captures the general concept of tractable properties of sequences with length less than or equal to grossone.