The limits of computation
File(s)s10516-021-09561-8.pdf (1.19 MB)
Published version
Author(s)
Powell, Andrew
Type
Journal Article
Abstract
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 algo- rithms 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.
Date Issued
2022-12-01
Date Acceptance
2021-04-26
Citation
Axiomathes, 2022, 32, pp.991-1011
ISSN
1572-8390
Publisher
Springer
Start Page
991
End Page
1011
Journal / Book Title
Axiomathes
Volume
32
Copyright Statement
© Crown 2021. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
License URL
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000654970300001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Arts & Humanities
Philosophy
Computation
Lambda calculus
Type theory
2ND-ORDER LOGIC
CALCULUS
Publication Status
Published
Date Publish Online
2021-05-26