Title | Truncation and Semi-Decidability Notions in Applicative Theories |
Publication Type | Journal Article |
Year of Publication | 2018 |
Authors | Jäger, G, Rosebrock, T, Sato, K |
Journal | The Journal of Symbolic Logic |
Volume | 83 |
Issue | 03 |
Pagination | 967-990 |
Abstract | BON+ is an applicative theory and closely related to the first order parts of
the standard systems of explicit mathematics. As such it is also a natural framework
for abstract computations. In this article we analyze this aspect of BON+ more closely.
First a point is made for introducing a new operation τN , called truncation, to obtain a
natural formalization of partial recursive functions in our applicative framework. Then we
introduce the operational versions of a series of notions that are all equivalent to semi-
decidability in ordinary recursion theory on the natural numbers, and study their mutual
relationships over BON+ with τN . |
URL | http://www.iam.unibe.ch/ltgpub/2016/jarosa16.pdf |
DOI | 10.7892/boris.125568 |