Operative vs. combinatory spaces

Extract

The algebraic systems of combinatory spaces [3] and operative spaces [1] have been designed to provide appropriate settings for the development of abstract recursion theory. As shown in [1, Chapter 27], these systems are closely related; namely, every combinatory space has a companion operative space with a storing operation St such that Skordev recursiveness in the former equals st-recursiveness in the latter. The problem of characterization of those operative spaces which have companion combinatory spaces was solved in [2] by introducing a class of operative spaces called Skordev spaces and showing that these give an alternative axiomatics of Skordev's combinatory spaces.

In this paper we study operative spaces with two special constants S₁ and S₂ which, in computer science terms, axiomatize the availability of stacking facility. We establish that any such space has a Skordev subspace and, moreover, all Skordev spaces can be obtained in this way. The construction ensures that st-recursiveness in the Skordev space concerned is equivalent to recursiveness in S₁ and S₂ in the wider operative space. Therefore, it quite unexpectedly turns out that Skordev recursiveness can be expressed via relative recursiveness in operative spaces in a straightforward manner, without employing higher spaces as done in [1].