Computable Execution Traces

In Alexandra Silva, Renata Wassermann & Ruy de Queiroz (eds.), Logic, Language, Information, and Computation: 27th International Workshop, Wollic 2021, Virtual Event, October 5–8, 2021, Proceedings. Springer Verlag. pp. 235-251 (2021)
  Copy   BIBTEX

Abstract

This paper gives an execution trace set based account of computability by imposing restrictions on sets of arbitrary sequences of objects, based on a supplied stock of unary tests and binary operations. This account of finite control computability provides a highly general, top down perspective on computability. We prove equivalence with the Turing machine model, under appropriate assumptions, and show how finite control computability can be used to provide a unified account of computability across multiple levels of abstraction.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/978-3-030-88853-4_15

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,174

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Turing computations on ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.
Logic, Language, Information, and Computation: 27th International Workshop, Wollic 2021, Virtual Event, October 5–8, 2021, Proceedings.Alexandra Silva, Renata Wassermann & Ruy de Queiroz (eds.) - 2021 - Springer Verlag.
Effective Computation by Humans and Machines.Shagrir Oron - 2002 - Minds and Machines 12 (2):221-240.
Meaning and Computing: Two Approaches to Computable Propositions.Ivo Pezlar - 2021 - In Alexandra Silva, Renata Wassermann & Ruy de Queiroz (eds.), Logic, Language, Information, and Computation: 27th International Workshop, Wollic 2021, Virtual Event, October 5–8, 2021, Proceedings. Springer Verlag. pp. 100-116.
Should Computability Be Epistemic? a Logical and Physical Point of View.Florent Franchette - 2016 - Philosophies 1 (1):15--27.
Computability and the game of cops and robbers on graphs.Rachel D. Stahl - 2022 - Archive for Mathematical Logic 61 (3):373-397.
Formalized Soundness and Completeness of Epistemic Logic.Asta Halkjær From - 2021 - In Alexandra Silva, Renata Wassermann & Ruy de Queiroz (eds.), Logic, Language, Information, and Computation: 27th International Workshop, Wollic 2021, Virtual Event, October 5–8, 2021, Proceedings. Springer Verlag. pp. 1-15.
Weak computability and representation of reals.Xizhong Zheng & Robert Rettinger - 2004 - Mathematical Logic Quarterly 50 (4-5):431-442.
Concrete Digital Computation: What Does it Take for a Physical System to Compute? [REVIEW]Nir Fresco - 2011 - Journal of Logic, Language and Information 20 (4):513-537.
Inside the Muchnik degrees I: Discontinuity, learnability and constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.

Analytics

Added to PP
2022-03-10

Downloads
6 (#1,697,385)

6 months
2 (#1,688,095)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references