Computation and Hypercomputation

Andrew Powell
Additional contact information
Andrew Powell: Institute for Security Science and Technology, Imperial College, South Kensington Campus, London SW7 2AZ, UK

Mathematics, 2022, vol. 10, issue 6, 1-16

Abstract: This paper shows some of the differences and similarities between computation and hypercomputation, the similarities relating to the complexity of propositional computation and the differences being the propositions that can be decided computationally or hypercomputationally. The methods used are ordinal Turing machines with infinitely long programs and diagonalization out of computing complexity classes. The main results are the characterization of inequalities of run time complexities of serial, indeterministic serial and parallel computers and hypercomputers and the specification of a hierarchy of hypercomputers that can hypercompute the truths of all propositions in the standard class model of set theory, the von Neumann hierarchy of pure sets.

Keywords: computation; diagonalization; hypercomputation; recursion theory; von Neumann hierarchy of pure sets (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/6/997/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/6/997/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:6:p:997-:d:775254

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().