Cantor’s Diagonal Argument for the Existence of Transfinite Numbers (Wikipedia, 2023)
You can also download and read or share a .pdf of the complete text of this essay HERE.
How and Why to Perform Uncomputable Functions
When I look at Gödel’s proof of his undecidability theorem…. [, t]he proof is a soaring piece of architecture, as unique and as lovely as Chartres Cathedral…. It destroyed Hilbert’s dream of reducing all mathematics to a few equations, and replaced it with a greater dream of mathematics as an endlessly growing realm of ideas…. Every formalization of mathematics raises questions that reach beyond the limits of the formalism into unexplored territory. (Dyson, 2008)
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 foundational for all logic and mathematics. Moreover, insofar as all formal and natural sciences presuppose and use logic and/or mathematics, the very idea of a function is also 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.
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)
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 boldfacing 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, 1931/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. And, since every “artificial intelligence,” aka AI, no matter how sophisticated or tricked-up with fancy bells and whistles it might be, is nothing but a digital computer (Turing, 1950), therefore AI has inherent formal limits too (Keller, 2023; Landgrebe and Smith, 2022).
Now, in addition to uncomputability/undecidability by virtue of non-denumerable domains of objects, the other principal source of uncomputability/undecidability has to do with the very idea of a rule-governed mapping. In order to do proofs beyond computability/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, 2006: pp. 158-168, 2021a: ch. XII).
The rule-following paradox has two versions: (i) no rule can be applied without requiring a meta-rule to interpret the first rule, and so-on, which entails a vicious regress of rules (Immanual 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).
Turing’s halting problem in the logical theory of digital computation is in fact a sub-species of the later Wittgenstein/Kripkenstein rule-following paradox. The halting problem, which is provably unsolvable, says:
there is no general algorithm for determining, from a description of an arbitrarily-selected computer program together with an arbitrarily-selected input, whether this program will either stop processing, i.e., be computable/decidable, or else continue processing forever, i.e., be uncomputable/undecidable. (Turing, 1936/1937; Boolos and Jeffrey, 1989: pp. 28-33, 41-42, 49-50)
Then we can translate the halting problem into the rule-following paradox just by substituting necessarily equivalent rule-terminology for computational terminology, with the appropriate substitutions in boldfaced text, as per this:
there is no general meta-rule for determining, from a description of an arbitrarily-selected rule together with an arbitrarily-selected application of that rule, whether this rule expresses either a computable/decidable function or else an uncomputable/undecidable function.
In other words, there is no general meta-rule for determining how to go on applying an arbitarily-selected rule, given an arbitarily-selected application of that rule. So the rule-following paradox and the halting problem are essentially the same problem. They both say that partial functions (arbitrarily-selected inputs; arbitrarily-selected applications of a rule) necessarily underdetermine complete functions (complete processing sequences; all the rule applications under a computable/decidable or uncomputable/undecidable rule), and that attempting to determine precisely which complete function it is and also which kind of complete function it is—computable/decidable or uncomputable/undecidable—by appealing to a higher-order function (general algorithm; meta-rule), leads to a vicious regress of higher-order functions.
All these considerations lead me to assert a general thesis:
for every uncomputable/undecidable function whatsoever in the formal or natural sciences, in order to explain the effective operations of that function beyond uncomputability/undecidability, we postulate an innately-specified rational human capacity, or a unified set of such capacities, for effectively performing that function by means of an essentially creative (i.e., essentially free or spontaneous, essentially organic or non-mechanical, and essentially a priori or strictly underdetermined by any and all contingent, sensible facts) act of human rationality .
Just to give it a conveniently short name, let’s call this thesis creative human rationality for uncomputable functions. And here are some examples that confirm the thesis of creative human rationality for uncomputable functions:
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, 1931/1967; Feferman, 2006);
actually discovering whether the arithmetical function someone is performing is “plus” or “quus,” by knowing intuitively how to follow the rule in new applications of it (Kripke, 1982; Hanna, 2006: ch. 6);
knowing the truth of the universal proto-logical principles that provide the unique solution to the fully generalized and strengthened logocentric predicament (Hanna, 2006: ch. 3, 2023b);
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 or nonsensical for any actual or possible Optical Character Recognition (OCR) system to “read” (Hanna, 2023a).
In my opinion, creative human rationality for uncomputable functions is clearly and distinctly true, precisely because it’s the best overall explanation of all the manifestly real facts about uncomputable/undecidable functions in the formal or natural sciences and the effectively performed functions that transcend them. To be sure, in order to accept creative human rationality for uncomputable functions, one also has to accept a broadly Kantian conception of rational human cognition, knowledge, and the formal or natural sciences, including what I call mathematics for humans, physics for humans, sensible set theory, logical cognitivism, Kantian intuitionism, Kantian structuralism, essentialist content non-conceptualism, Kantian modal dualism, the epigenetic model of the mind, and weak transcendental idealism (Hanna, 2002, 2006, 2015: esp. chs. 2 and 4-8, esp. section 7.3, 2022a: esp. section 4.4, and appendix 4, 2022b, 2022c). But each of these unfamiliarly-named doctrines is supported by compellingly strong arguments and reasons, independently of this particular thesis—i.e., creative human rationality for uncomputable functions—and the particular logico-mathematical and epistemic issues and problems that are addressed by it. And 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 the thesis of creative human rationality for uncomputable functions is in fact rationally overwhelming and, as they say, knockdown.
So now I’ll conclude by using a simple question-&-answer format—Q1: how to perform uncomputable functions? A1: by means of creative human rationality. Q2: why to perform uncomputable functions? A2: because it conclusively demonstrates that we’re rational human minded animals with dignity, and not just tricked-up Turing machines (Hanna, 2023a, 2023c, 2023d).[i]
NOTE
[i] I’m grateful to Elma Berisha for thought-provoking correspondence on and around the main topics of this essay.
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.
(Dyson, 2008). Dyson, F. The Scientist as Rebel. New York: NRYB Collections.
(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 at URL = <https://www.academia.edu/160391/The_nature_and_significance_of_G%C3%B6dels_incompleteness_theorems>.
(Gödel, 1931/1967). Gödel, K. “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” In J. van Heijenoort (ed.), From Frege to Gödel. Cambridge MA: Harvard Univ. Press. Pp. 596-617).
(Hanna, 2002). Hanna, R. ) “Mathematics for Humans: Kant’s Philosophy of Arithmetic Revisited.” European Journal of Philosophy 10: 328-353.
(Hanna, 2006). Hanna, R. Rationality and Logic. Cambridge: MIT Press. Available online in preview at URL = <https://www.academia.edu/21202624/Rationality_and_Logic>.
(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. “Physics For Humans: Kant, Natural Science, and The Neo-Aristotelian Natural Power Grid.” Revue romaine de philosophie 66: 197-216. Also available online at URL = <http://www.institutuldefilosofie.ro/page.php?146> and in preview HERE.
(Hanna, 2023a). “Are There Some Legible Texts That Even The World’s Most Sophisticated Robot Can’t Read?” Unpublished MS. Available online HERE.
(Hanna, 2023b). Hanna, R. ““The Fully Generalized and Strengthened Logocentric Predicament.” Unpublished MS. Available online HERE.
(Hanna, 2023c). Hanna, R. “How and Why ChatGPT Failed The Turing Test.” Unpublished MS. Available online at URL = <https://www.academia.edu/94870578/How_and_Why_ChatGPT_Failed_The_Turing_Test_January_2023_version_>.
(Hanna, 2023d). Hanna, R. “Don’t Pause Giant AI Experiments: Ban Them.” Unpublished MS. Available online at URL = <https://www.academia.edu/97882365/Don_t_Pause_Giant_AI_Experiments_Ban_Them_April_2023_version_>.
(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]
(Keller, 2023). Keller, A. “Artificial, But Not Intelligent: A Critical Analysis of AI and AGI.” Against Professional Philosophy. 5 March. Available online at URL = <https://againstprofphil.org/2023/03/05/artificial-but-not-intelligent-a-critical-analysis-of-ai-and-agi/>.
(Kripke, 1982). Kripke, S. Wittgenstein on Rules and Private Language. Cambridge, MA: Harvard Univ. Press.
(Landgrebe and Smith, 2022). Landgrebe, J. and Smith, B. Why Machines Will Never Rule the World: Artificial Intelligence without Fear. London: Routledge.
(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.
(Turing, 1950). Turing, A. “Computing Machinery and Intelligence.” Mind 59: 433–460.
(Wikipedia, 2023). Wikipedia. “Cantor’s Diagonal Argument.” Available online at URL = <https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument>.
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!
