By Robert Hanna
***
You can also download and read or share a .pdf of the complete text of this essay HERE.
***
Uncomputable Functions and Beyond
A function is a rule-governed mapping from a set of objects (aka the “arguments” or “inputs”), to another set of objects (aka “the values” or “outputs”), and, along with the very ideas of a set and of an object, the very idea of a function is not only foundational for all logic and mathematics, but also, insofar as all formal and natural sciences presuppose and use logic and/or mathematics, it’s foundational for all the formal and natural sciences.
Among the most important kinds of functions are computable functions, and in order to understand these, we need the notion of a Turing machine and its operations.
So, what is a Turing machine, and what are its operations?
Here’s a compact and elegant way of characterizing them:
No human being can write fast enough, or long enough, or small enough, to list all members of a… [d]enumerably infinite set [e.g., the positive integers] by writing out their names, one after another, in some notation. But humans can do something equally useful, in the case of certain [d]enumerably infinite sets: They can give explicit instructions for determining the nth member of the set for an arbitrary finite n. Such instructions are to be given quite explicitly, in a form in which they could be followed by a computing machine, or by a human who is capable of carrying out only very elementary operations on symbols. The problem will remain, that for all but a finite number of values of n it will be physically impossible for any human or any machine to actually carry out the computation, due to limitations on the time available for computation, and on the speed with which single steps of the computation can be carried out, and on the amount of matter in the universe which is available for forming symbols. But it will make for clarity and simplicity if we ignore these limitations, thus working with a notion of computability which goes beyond what actual men or machines can be sure of doing…. The notion of computation can be made precise in many different ways, corresponding to different possible answers to such questions as the following. “Is the computation to be carried out on a linear tape, or on a rectangular grid, or what? If a linear tape is used, is the tape to have a beginning but no end, or is it to be endless in both directions? Are the squares into which the tape is divided to have addresses (like addresses of houses on a street) or are we to keep track of where we are by writing special symbols in suitable squares (as one might mark a trail in the woods by marking trees)? And so-on…. Since there is no end to the possible variations in detailed characterizations of the notions of computability and effectiveness, one must finally accept or reject the thesis [aka “Church’s thesis,” aka “the Church-Turing thesis”] … that the set of functions computable in our sense [i.e., the set of recursive functions] is identical with the set of functions that men or machines would be able to compute by whatever effective method, if limitations on time, speed, and material were overcome. (Boolos and Jeffrey, 1989: pp. 19–20, square-bracketted material added; see also Turing, 1936/1937; Church, 1937)
At the top of this essay, I’ve also displayed a diagram of one possible kind of Turing machine, in order to make that compact and elegant description even more intuitive.
So in other and fewer words, a Turing machine is a digital computer, and its operations are all and only the computations that fall within the scope of recursive functions (Turing, 1936–1937; Church, 1937).
Recursive functions, in turn, are step-by-step algorithms, routines, or rule-governed sequences, such that precisely the same algorithm/routine/rule-governed sequence is applied to the result of the preceding step, in a denumerable (countable) sequence, up to some arbitarily-fixed terminal step.
Something that’s absolutely essential to note about Turing machines/digital computers from the get-go, however, is that
certain functions are not computable, and that certain [d]enumerable sets are not effectively (mechanically) [d]enumerable — even if physical limitations on time, speed, and amount of material could somehow be overcome. (Boolos and Jeffrey, 1989: p. 19, square bracketting and underlining added)
In particular, it’s logically demonstrable that truth and proof in Peano arithmetic, and also in classical first-order polyadic predicate logic, aka elementary logic, are uncomputable, aka undecidable (Church, 1936; Gödel, 1967; Boolos and Jeffrey, 1989: chs. 10, 15, 16, 21, 22, 28).
More generally, all functions over non-denumerable domains — for example, over transfinite sets like the real numbers; but also over finite or infinite domains that cannot be divided or partitioned into any denumerable set of discrete, determinate individuals or units, owing to irreducible complementarity, holism, partial overlapping, or ontological indeterminacy, gappiness, or vagueness — are not computable or decidable, precisely because they’re not recursive functions.
Therefore, digital computation has inherent formal limits.
Can these specific inherent formal limits of digital computation — that is, uncomputability or undecidability by virtue of non-denumerable domains — be transcended?
Yes, provided that we accept what I call sensible set theory (Hanna, 2022: appendix 4), as follows.
For the purposes of this essay, by set theory I mean, in general, classical Cantorian set theory, but more specifically Zermelo’s and Fraenkel’s well-ordered set theory plus the Axiom of Choice, the latter of which is equivalent to licensing the power-set operation (constructing the set of all subsets) on finite or infinite sets, aka ZFC (Zermelo, 1930, 1967a, 1967b, 1967c; Hallett, 1984; Potter, 1990: ch. 7).
Now, according to Immanuel Kant’s Critical philosophy, the objects of human sensibility (Sinnlichkeit), which is the essentially non-conceptual mode of rational human cognition, specifically include
(i) the objects of empirical intuition or sense perception, including objects of either inner sense (phenomenal subjective experience, or consciousness) or outer sense (essentially embodied awareness of the external world),
(ii) the objects of imagination, including mental imagery, objects of fictional imagining, objects of projective anticipation about the future, the objects of episodic memory, objects in motion, and schematic objects, and
(iii) the objects of pure a priori intuition, namely, phenomenal space and phenomenal time, as “infinite given wholes” (Kant, 1998: pp. 155–192, 256–259, 273–274 A19–49/B33–73, B151–156, A140–143/B179–182; Hanna, 2006a: esp. chs. 1–2 and 6, 2020a).
In this way, the objects of human sensibility, aka sensible objects, are phenomena in the broadest sense of that term, and their nature is also essentially relational, in that their actual or really possible existence inherently requires
(i) intrinsic structural phenomenal spatial or temporal relations, and also
(ii) the actual or really possible existence of rational, conscious, self-conscious human cognizers possessing an innately specified capacity for sensibility (Hanna, 2006a: esp. chs. 1–2 and 6).
By a diametric contrast, again according to Kant’s Critical philosophy, noumena, aka supersensible objects, are specifically the objects of the rational human conceptual mode of cognition, aka thinking, hence they’re specifically “entities of the understanding” or Verstandeswesen (Kant, 1998: p. 360, B306), such that, if they were to exist, they would be knowable only by a superhuman being possessing “intellectual intuition,” and furthermore these objects would be non-sensible, non-spatiotemporal, and have intrinsic non-relational essences, i.e., they would have “lonely” natures, such that they would be able to exist on their own even if nothing else existed in the world (Kant, 1998: pp. 1919–192, 354–365, B71–72, A235–260/B294–315).
In view of all that, then sensible set theory is set theory that’s restricted to all and only sensible objects.
In turn, for every function in the formal or natural sciences that’s uncomputable or undecidable by virtue of non-denumerable domains of objects, in order to explain the effective operations of that function beyond uncomputability or undecidability, we postulate an innately specified rational human capacity, or a unified set of such capacities, for effectively performing that function (Hanna, 2015: ch. 8; Hanna, 2022: appendices 1, 3, and 4).
This proposal, when fully worked out, leads to the doctrines that I call Kantian intuitionism and Kantian structuralism, in order to explain a priori knowledge, not only in all the formal and natural sciences specifically, but also in philosophy more generally (Hanna, 2015: chs. 5–8).
Now, in addition to uncomputability or undecidability by virtue of non-denumerable domains of objects, the other principal source of uncomputability or undecidability has to do with the very idea of a rule-governed mapping.
In order to do proofs beyond computability or decidability in classical first-order polyadic predicate logic or elementary logic, or in any richer system that contains classical classical first-order polyadic predicate logic or elementary logic as a fragment or proper part, both rules and also rule-following are needed, and, as it turns out, rule-following is an irreducibly normative activity that presupposes conscious and self-conscious rational cognizers, as members of a community of language-users, whenever it exceeds mere boolean computability, as the later Wittgenstein’s and also Saul Kripke’s or “Kripkenstein’s” solution to the rule-following paradox shows (Kripke, 1982; Hanna, 2006b: pp. 158–168, 2021a: ch. XII).
The rule-following paradox has two versions:
(i) no rule can be applied without requiring another rule to interpret the first rule, and so-on, which entails a vicious regress of rules (Kant also explicitly recognized this problem at 1998: pp. 268–269, A132–134/B171–174), and
(ii) given only a finite and denumerable set of inputs (arguments) and outputs (values) to a given function, i.e., given only a partial function, nevertheless an indeterminately large number of different rules can describe the same set of inputs/outputs and also diverge on subsequent inputs/outputs, so therefore the different rules will determine different complete functions, even given the same partial functions, and there’s no purely mechanical, materialist/physicalist, or private/solipsistic way to avoid this underdetermination of the rules by those partial functions.
Moreover, according to later Wittgenstein and “Kripkenstein” alike — and I strongly agree — in order to fix the interpretation and applications of a rule, language-using communities of conscious and self-conscious rational human cognizers are needed in order to figure out “how to go on” and therefore also to decide what counts as correct, as opposed to incorrect, applications of the rule (Hanna, 2006b: pp. 158–168, 2021: ch. XIII).
Anticipating later Wittgenstein and “Kripkenstein” by roughly 200 years, Kant calls this very same ability “so-called mother-wit” or Mutterwitz, and in turn this ability is essentially bound up with the innately-specified conscious and self-conscious rational human capacity for judgment, or what he calls “the natural power of judgment” or natürlicher Urteilskraft (Kant, 1998: pp. 268–269, A133–134/B172–174), not only for “determining” judgment, which subsumes individual objects under given general concepts, but also and especially for “reflecting” judgment, which projects from individual objects to general concepts, either inductively or abductively (Kant, 2000: pp. 66–68, Ak 5: 179–181; Hanna, 2017).
All these considerations lead me to assert a general thesis:
for every uncomputable or undecidable function whatsoever in the formal or natural sciences, in order to explain the effective operations of that function beyond uncomputability or undecidability, we postulate an innately-specified rational human capacity, or a unified set of such capacities, for effectively performing that function.
Just to give it a conveniently short name, let’s call this thesis rational anthropology for uncomputable functions.
And here are some examples that confirm the thesis: doing proofs in elementary logic using inference rules that essentially invoke polyadic quantification (Church, 1936); performing Cantor’s diagonal argument for the existence of transfinite numbers (Cantor, 1891, 2019); knowing the truth of a Gödel sentence that’s a new mathematical axiom (Gödel, 1967; Feferman, 2006); actually discovering whether the arithmetical function one is performing is “plus” or “quus,” by knowing intuitively how to follow the rule in new applications of it (Kripke, 1982; Hanna, 2006b: ch. 6); experimentally tracking the actual path of a particle guided by a Bohmian “pilot wave” in The Two Slit Experiment (Bohm, 1952; Hanna, 2022a: section 4.3); more fancifully and thought-experimentally, imaginatively experimentally tracking the actual fate of Schrödinger’s cat (Schrödinger, 1980); and actually reading a sentence in English that’s too garbled for any Optical Character Recognition (OCR) system to “read” (Hanna, 2022c: section 00).
In my opinion, rational anthropology for uncomputable functions is clearly and distinctly true, precisely because it’s the best overall explanation of all the manifestly real facts about uncomputable or undecidable functions in the formal or natural sciences and the effectively performed functions that transcend them.
To be sure, in order to accept rational anthropology for uncomputable functions, one also has to accept sensible set theory and a broadly Kantian conception of rational human cognition and knowledge, including Kantian intuitionism, Kantian structuralism, essentialist content non-conceptualism, analytic and synthetic a priori truths, the epigenetic model of the mind, and weak transcendental idealism (Hanna, 2015: esp. chs. 2 and 4–8, esp. section 7.3, 2022a: esp. section 4.4, and appendix 4, 2022b).
But each of these doctrines is supported by compellingly strong arguments and reasons, independently of this particular thesis — i.e., rational anthropology for uncomputable functions — and the particular logico-mathematical and epistemic issues and problems that are addressed by it.
So, when we self-consciously bracket-out and suspend the (admittedly powerful and never-to-be-underestimated) purely ideological influence of what I’ve called the Kant wars — i.e., classical and contemporary dogmatic anti-Kantianism inside professional academic philosophy and indeed outside it too (Hanna, 2020b) — then I think that the all-things-considered case in support of rational anthropology for uncomputable functions is in fact rationally overwhelming and, as they say, knockdown.
REFERENCES
(Bohm, 1952). Bohm, D. “A Suggested Interpretation of the Quantum Theory in Terms of ‘Hidden’ Variables, I and II.” Physical Review, 85(2): 166–193.
(Boolos and Jeffrey, 1989). Boolos, G. and Jeffrey, R. Computability and Logic.3rd edn., Cambridge: Cambridge Univ. Press.
(Cantor, 1891). Cantor, G. “Ueber eine elementare Frage der Mannigfaltigkeitslehre.” Jahresbericht der Deutschen Mathematiker-Vereinigung 1: 75–78.
(Cantor, 2019). Cantor, G. “A Translation of G. Cantor’s ‘Ueber eine elementare Frage der Mannigfaltigkeitslehre’.” Trans. P.P. Jones et al. 23 August. Available online HERE.
(Church, 1937). Church, A. “Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem.” Journal of Symbolic Logic 2: 42–43.
(Feferman, 2006). Feferman, S. “The Nature and Significance of Gödel’s Incompleteness Theorems.” Institute for Advanced Study, Princeton: Gödel Centenary Program. 17 November. Available online HERE.
(Gödel, 1967). Gödel, K. “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” In (van Heijenoort, 1967: 596–617).
(Hallett, 1984). Hallett, G. Cantorian Set Theory and Limitation of Size. Oxford: Oxford Univ. Press.
(Hanna, 2006a). Hanna, R. Kant, Science, and Human Nature. Oxford: Clarendon/OUP. Also available online in preview HERE.
(Hanna, 2015). Hanna, R. Cognition, Content, and the A Priori: A Study in the Philosophy of Mind and Knowledge. THE RATIONAL HUMAN CONDITION, Vol. 5. Oxford: Oxford Univ. Press. Also available online in preview HERE.
(Hanna, 2017). Hanna, R. “Kant’s Theory of Judgment.” In E.N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Winter Edition. Available online at URL = <https://plato.stanford.edu/archives/win2017/entries/kant-judgment/>.
(Hanna, 2020a). Hanna, R., “The Essential Non-Conceptuality of the Imagination.” Contemporary Studies in Kantian Philosophy 5: 53–72. Available online at URL = <https://www.cckp.space/single-post/2020/06/15/CSKP5-2020-The-Essential-Non-Conceptuality-of-the-Imagination>.
(Hanna, 2020b). Hanna, R. “The Kant Wars and The Three Faces of Kant.” Contemporary Studies in Kantian Philosophy 5: 73–94. Available online at URL = <https://www.cckp.space/single-post/2020/06/15/CSKP5-2020-The-Kant-Wars-and-The-Three-Faces-of-Kant>.
(Hanna, 2021). Hanna, R., The Fate of Analysis: Analytic Philosophy From Frege to The Ash-Heap of History. New York: Mad Duck Coalition. Affordably available in hardcover, softcover, and Epub at URL = <https://themadduckcoalition.org/product/the-fate-of-analysis/>.
(Hanna, 2022a). Hanna, R. The Philosophy of the Future: Uniscience and the Modern World. Unpublished MS. Available online HERE.
(Hanna, 2022b). Hanna, R. “Analytic Philosophy, Rational Anthropology, and The Epigenetic Model of the Mind.” Unpublished MS. Available online HERE.
(Hanna, 2022c). Hanna, R. “Caveat Lector: Six Investigations in The Philosophy of Reading.” Unpublished MS. Available online HERE.
(Kant, 1998). Kant, I. Critique of Pure Reason. Trans. P. Guyer and A. Wood. Cambridge: Cambridge Univ. Press. (1781/1787, Ak 3, 4: 1–252).
(Kant, 2000). Kant, I. Critique of the Power of Judgment. Trans. P. Guyer and E. Matthews. Cambridge: Cambridge Univ. Press, 2000. [1790, Ak 5: 165–485]
(Kripke, 1982). Kripke, S. Wittgenstein on Rules and Private Language. Cambridge, MA: Harvard Univ. Press.
(Potter, 1990). Potter, M. Sets: An Introduction. Oxford: Oxford Univ. Press.
(Schrödinger, 1980). Schrödinger, E. “The Present Situation in Quantum Mechanics.” Trans. J.D. Trimmer. Proceedings of the American Philosophical Society 124: 323–338.
(Turing, 1936/1937). Turing, A. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society 42: 230–265, with corrections in 43: 644–546.
(van Heijenoort, 1967). van Heijenoort, J. (ed.) From Frege to Gödel. Cambridge MA: Harvard Univ. Press.
(Zermelo, 1930). Zermelo, E. “Über Grenzzahlen und Mengenbereiche.” Fundamenta Mathematicae 16: 29–47.
(Zermelo, 1967a). Zermelo, E. “Proof That Every Set Can Be Well-Ordered.” In (van Heijenoort, 1967: pp. 139–141).
(Zermelo, 1967b). Zermelo, E. “A New Proof of the Possibility of a Well-Ordering.” In (van Heijenoort, 1967: pp. 183–198).
(Zermelo, 1967c). Zermelo, E. “Investigations in the Foundations of Set Theory I.” In (van Heijenoort, 1967: pp. 199–215).
AGAINST PROFESSIONAL PHILOSOPHY REDUX 735
Mr Nemo, W, X, Y, & Z, Monday 31 October 2022
Against Professional Philosophy is a sub-project of the online mega-project Philosophy Without Borders, which is home-based on Patreon here.
Please consider becoming a patron!
