Extensions of Scott's Graph Model and Kleene's Second Algebra

J. van Oosten, Niels Voorneveld

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We use a way to extend partial combinatory algebras (pcas) by forcing them to represent certain functions. In the case of Scott’s Graph Model, equality is computable relative to the complement function. However, the converse is not true. This creates a hierarchy of pcas which relates to similar structures of extensions on other pcas. We study one such structure on Kleene’s Second Algebra and one on a pca equivalent but not isomorphic to it. For the recursively enumerable sub-pca of the Graph model, results differ as we can compute the (partial) complement function using the equality.
Original languageEnglish
Pages (from-to)5-22
JournalIndagationes Mathematicae
Volume29
Issue number1
DOIs
Publication statusPublished - Feb 2018

Fingerprint

Dive into the research topics of 'Extensions of Scott's Graph Model and Kleene's Second Algebra'. Together they form a unique fingerprint.

Cite this