The Limits of Computation
Bibliographic Data
| ID | 21655327 |
|---|---|
| Authors | Andrew Powell (0000-0002-3470-1038, Imperial College London, corresponding author) |
| Year | 2022 |
| Volume | 32 |
| Issue | 6 |
| Pages | 991-1011 |
| Publication date | 2022-12-01 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Axiomathes (JOURNAL) |
| Journal identifiers | ISSN: 1122-1151 • E-ISSN: 1572-8390 |
| Publisher | Springer Science and Business Media LLC (PUBLISHER) |
| DOI | 10.1007/s10516-021-09561-8 |
| OpenAlex | W3165024031 |
| Language | EN |
| References cited | 49 |
This article provides a survey of key papers that characterise computable functions, but also provides some novel insights as follows. It is argued that the power of algorithms is at least as strong as functions that can be proved to be totally computable in type-theoretic translations of subsystems of second-order Zermelo Fraenkel set theory. Moreover, it is claimed that typed systems of the lambda calculus give rise naturally to a functional interpretation of rich systems of types and to a hierarchy of ordinal recursive functionals of arbitrary type that can be reduced by substitution to natural number functions
Algebra over a field · Algorithm · Computable function · Computation · Discrete mathematics · Epistemology · Hierarchy · Lambda calculus · Ontology · Pure mathematics · Computability, Logic, AI Algorithms · Computer Science · Logic, programming, and type systems · Logic, Reasoning, and Knowledge · Mathematics · Theoretical Computer Science
| Highly cited | No |
|---|