Zobrazeno 1 - 10
of 112
pro vyhledávání: '"Terwijn, Sebastiaan A."'
Autor:
Terwijn, Sebastiaan A.
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 those. We also point out several open problems connected to these.
Externí odkaz:
http://arxiv.org/abs/2402.03069
Autor:
Terwijn, Sebastiaan A.
We investigate completions of partial combinatory algebras (pcas), in particular of Kleene's second model $\mathcal{K}_2$ and generalizations thereof. We consider weak and strong notions of embeddability and completion that have been studied before i
Externí odkaz:
http://arxiv.org/abs/2312.14656
Autor:
Terwijn, Sebastiaan A.
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 of them have high complexity. We show that although there do not exist
Externí odkaz:
http://arxiv.org/abs/2307.12685
Autor:
Golov, Anton, Terwijn, Sebastiaan A.
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 embeddings between relativizations of Kleene's models, of van Oosten'
Externí odkaz:
http://arxiv.org/abs/2204.03553
Autor:
Golov, Anton, Terwijn, Sebastiaan A.
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 it to show that for the class of divisible numberings, lowness and rel
Externí odkaz:
http://arxiv.org/abs/2101.12271
Autor:
Shafer, Paul, Terwijn, Sebastiaan A.
For every partial combinatory algebra (pca), we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca's, i.e. the smallest ordinals where these relations become equal. We show that the closure ordin
Externí odkaz:
http://arxiv.org/abs/2010.12452
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Terwijn, Sebastiaan A.
We discuss the (non)effectivity of Arslanov's completeness criterion. In particular, we show that a parameterized version, similar to the recursion theorem with parameters, fails. We also discuss the parameterized version of another extension of the
Externí odkaz:
http://arxiv.org/abs/1804.01522
Autor:
Terwijn, Sebastiaan A.
Publikováno v:
J. symb. log. 83 (2018) 1683-1690
We consider two generalizations of the recursion theorem, namely Visser's ADN theorem and Arslanov's completeness criterion, and we prove a joint generalization of these theorems.
Externí odkaz:
http://arxiv.org/abs/1803.10843
Publikováno v:
Annals of Pure and Applied Logic 168 (2017), no. 4, 804--823. Preliminary version in: Computability in Europe, Lecture Notes in Computer Science 9136 (2015), 44--53
We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the con
Externí odkaz:
http://arxiv.org/abs/1712.05875