Truncation and Semi-Decidability Notions in Applicative Theories

Jäger, Gerhard; Rosebrock, Timotej Alexander; Sato, Kentaro (2018). Truncation and Semi-Decidability Notions in Applicative Theories. The journal of symbolic logic, 83(03), pp. 967-990. Cambridge University Press 10.1017/jsl.2018.34

[img] Text
jarosa16.pdf - Accepted Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (452kB) | Request a copy

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 .

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG)
08 Faculty of Science > Institute of Computer Science (INF)

UniBE Contributor:

Jäger, Gerhard Max; Rosebrock, Timotej Alexander and Sato, Kentaro

Subjects:

000 Computer science, knowledge & systems
500 Science > 510 Mathematics

ISSN:

0022-4812

Publisher:

Cambridge University Press

Language:

English

Submitter:

Lukas Jaun

Date Deposited:

10 May 2019 12:09

Last Modified:

23 Oct 2019 16:47

Publisher DOI:

10.1017/jsl.2018.34

BORIS DOI:

10.7892/boris.125568

URI:

https://boris.unibe.ch/id/eprint/125568

Actions (login required)

Edit item Edit item
Provide Feedback