8 citations · 20 across the 21 of their papers we have counts for
23 papers
Nonembeddings of Combinatory Algebras
Patrick Lutz, Paul Shafer, Sebastiaan A. Terwijn
In the theory of combinatorial algebras, there is a sequence of embeddings between Kleene's second model, van Oosten's model, and Scott's graph model. We prove that none of these e…
Fixed Point Theorems in Computability Theory
Sebastiaan A. Terwijn
We give a quick survey of the various fixed point theorems in computability theory, partial combinatory algebra, and the theory of numberings, as well as generalizations based on t…
Completions of Kleene's second model
Sebastiaan A. Terwijn
We investigate completions of partial combinatory algebras (pcas), in particular of Kleene's second model and generalizations thereof. We consider weak and strong n…
The complexity of completions in partial combinatory algebra
Sebastiaan A. Terwijn
We discuss the complexity of completions of partial combinatory algebras, in particular of Kleene's first model. Various completions of this model exist in the literature, but all…
Embeddings between partial combinatory algebras
Anton Golov, Sebastiaan A. Terwijn
Partial combinatory algebras are algebraic structures that serve as generalized models of computation. In this paper, we study embeddings of pcas. In particular, we systematize the…
Fixpoints and relative precompleteness
Anton Golov, Sebastiaan A. Terwijn
We study relative precompleteness in the context of the theory of numberings, and relate this to a notion of lowness. We introduce a notion of divisibility for numberings, and use…