Computation in Non-Classical Foundations?
Skip other details (including permanent urls, DOI, citation information)
: This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License. Please contact mpub-help@umich.edu to use this work in a way not covered by the license.
For more information, read Michigan Publishing's access and usage policy.
Abstract
The Church-Turing Thesis is widely regarded as true, because of evidence that there is only one genuine notion of computation. By contrast, there are nowadays many different formal logics, and different corresponding foundational frameworks. Which ones can deliver a theory of computability? This question sets up a difficult challenge: the meanings of basic mathematical terms (like "set", "function", and "number") are not stable across frameworks. While it is easy to compare what different frameworks say, it is not so easy to compare what they mean. We argue for some minimal conditions that must be met if two frameworks are to be compared; if frameworks are radical enough, comparison becomes hopeless. Our aim is to clarify the dialectical situation in this bourgeoning area of research, shedding light on the nature of non-classical logic and the notion of computation alike.
