Transcendental idealism and Post’s variant of the Church-Turing thesis

One of the exciting things in reading philosophy, its history in particular, is experiencing the tension between different schools of thought. This excitement turns to beauty if a clear synthesis emerges to reconcile the conflicting ideas. In the middle to late 18th century, as the Age of Enlightenment was giving way to the Romantic era, the tension was between rationalism and empiricism and the synthesis came from Immanuel Kant. His thought went on to influence or directly shape much of modern philosophy, and if you browse the table of contents of philosophical journals today then you will regularly encounter hermeneutic titles like “Kant on <semi-obscure modern topic>”. In this regard, my post is in keeping with modern practice because it could have very well been titled “Kant on computability”.

As stressed before, I think that it is productive to look at important concepts from multiple philosophical perspectives. The exercise can provide us with an increased insight into both the school of thought that is our eyes, and the concept that we behold. In this case, the concept is the Church-Turing thesis that states that anything that is computable is computable by a Turing machine. The perspective will be of (a kind of) cognitivism — thought consists of algorithmic manipulation of mental states. This perspective that can often be read directly into Turing, although Copeland & Shagrir (2013) better described him as a pragmatic noncognitivist. Hence, I prefer to attribute this view to Emil Post. Also, it would be simply too much of a mouthful to call it the Post-Turing variant of the Church-Turing thesis.

Rationalism, Empiricism, and the Inaugural Dissertation

Kant’s schooling and early thinking in philosophy was in line with continental rationalism. He was following in the footsteps of Descartes, Spinoza, and Leibniz as conveyed through the dogmatic Wolff. Rationalism privileged reason over experience, regarded ideas as innate, and emphasized certain, not probable, knowledge as the goal of philosophy (Lennon & Dea, 2012). It would not be too much of a stretch to call this the mathematician’s philosophy. In fact, both Descartes and Leibniz were very important mathematicians, and Spinoza had an extreme fondness of mathematics, structuring his Ethics in the axiomatic method of Euclid’s Elements. As such, it should come as no surprise that Kleene’s purely mathematical variant was a rationalist formulation of the Church-Turing thesis: computability is a real concept independent of our experience, and we can access it through our intuition by formulating different equivalent models like the Turing machine, lambda calculus, or rewrite systems. If pressed on the ontology of computability then hard-line platonists like Godel would argue for a realm of objective mathematics which we could access through the subjective mathematics of our particular formal systems and models of computation. A hard stance to swallow for non-mathematicians.

In middle-age, Kant was awakened from his dogmatic rationalist slumber by the British empiricists: Locke, Berkeley, and most importantly Hume. In many ways, the empiricists were the exact opposite of rationalists, they privileged the senses over reason, believed in no innate ideas — everything is learnt from sense experience — and relied on probable induction instead of deduction. This might seem familiar to most modern scientists, but the historic precedents did not go as far as today’s physicalism. In particular, Berkeley and Hume’s radical skepticism forced an idealist view on these early philosophers, who could not establish the probable existence of a world external to the mind. However, it is not clear how much Hume’s contemporaries were tuned to his idealism, so I won’t dwell on it too much. From this perspective, we infer what is computabale from our sensory experience. Turning our attention to the Church-Turing thesis, we get Gandy’s variant: any function computable by physical machine is computable by a Turing machine (Gandy, 1980). Where physical machines correspond to all computations we can experience through our senses. If pressed on ontology, Hume would probably change the subject, but a modern empiricist would argue that these computations are going on in a world external to our minds, and no process in this world can do more than a Turing machine.

In 1770, after fifteen years as an nonsalaried lecturer — deriving his income directly from payments by students who attended his classes — Kant was finally appointed to the chair in logic and metaphysics at the University of Königsberg (Rohlf, 2010). To celebrate, he wrote a dissertation Concerning the Form and Principles of the Sensible and Intelligible World where he attempted to reconcile rationalism and empiricism for the first time. In this Inaugural Dissertation (as it is usually referenced in the academic literature), Kant embraced, and at the same departed from, both the empiricists and rationalists by attributing two irreducible powers to cognition: sensibility and understanding. He associated a distinct world to each of the faculties, the sensible and the intelligible worlds. In this view, perception was the imposition of the intelligible world — of which we could have full understanding — onto the sensible world. He would later abandon this Platonic view that we are capable of insight into the intelligible world, but keep the distinction between the faculties of sensibility and understanding and how they structured perception.

Space: Newton, Leibniz, and Kant

The most important feature of the Inaugural Dissertation for our discussion is its introduced of another important tension: the hundred year old debate between Newton and Leibniz on the nature of space. Kant’s resolution began in this work, and was brought to completion in the Critique of Pure Reason; his views of space is the clearest way to understand transcendental idealism.

For Newton, space was part of the physical realm and a mind-independent immaterial substance that was inhabited by the matter that physics studies. In fact, everything that existed, existed somewhere in space. Even if the world was complete vacuum that nothingness would be in space. Newton had a realist and physicalist stance toward space, I am not sure how Newton would respond to the epistemic question of how we come to know space but I don’t think it is unreasonable to attribute to him an empiricist stance. I hope that you, dear reader, will grant me some analogy between this view of space and the physicalist variant of the Church-Turing thesis.

Leibniz’s view of space is a little harder to reconstruct, because his viewpoint was presented as many disjoint arguments and evolved during his life (Hartz & Cover, 1988), but I will try to present a rough sketch that I think Kant was addressing. For Leibniz, space was just the relational structure between the objects of the physical world. As such it was not mind-independent, although that isn’t saying much — nothing was really mind independent for Leibniz. If there was only vacuum then there would be no objects to be related to each other and space would not exist. In other words, our concept of space was ideal in the sense that it abstracted from properties of objects. However, these properties of objects that led to our understanding of space were real, for otherwise Leibniz’s identity of indiscernibles would force us to conclude that there is only one object. Note that although Leibniz’s presented this philosophy within a larger rationalist framework, the basics of it can be expressed in empiricist terms as abstracting a mathematical concept from physical objects and in this way is similar to Aristotle’s conception of space. By borrowing the terms of subjective and objective mathematics from Godel, I want to suggest the comparison of Leibniz’s rationalist interpretation of relational space to the purely mathematical variant of the Church-Turing thesis: ideal space corresponds to the models of our subjective mathematics and the realist properties corresponds to the true nature of ‘computable’ in the objective mathematics.

Kant reconciles (or less-charitably: sidesteps) this debate by producing an idealist absolute space. For Kant, space does not originate from the properties of external objects or from abstracting on our sense perception. Instead, space is a property of our organs of perceptions, and no matter what actual sense experience we have or even if we have none, we would still have the same concept of space. Further, since space is a property of our sense organs and thus structures the perception of all sensations, “everything that can come before us externally as an object” (Kant, 1787) is perceived within space (and time). In this way, space is absolute and not the relational abstraction of Leibniz. However, unlike Newton, Kant does not attribute this space to an external world that the objects of our sensation inhabit. Instead, “if we remove our own subject or even only the subjective constitution of the senses in general, then all constitution, all relations of objects in space and time, indeed space and time themselves would disappear, and as appearances they cannot exist in themselves, but only in us” (Kant, 1787). This combination of absolute and mind-dependent is Kant’s transcendental idealism.

For the purpose of our discussion, there are two salient features. First is the attribution of an absolute ideal to be an inescapable property of our way of sensing. Second is the more practical approach of taking two stances, one that is realist toward the sensible world, and a second that is realist toward the intelligible world, and instead reconciling them in an anti-realist, but still absolute, mind-dependent idea. I will apply these ideas to the Church-Turing thesis, but for a staunch Kantian this might seem redundant since transcendental idealism extends beyond just space. In fact, for Kant all of “the structure of mathematical reasoning is due to the structure of our apparatus of perception” (Hintikka, 1967). However, as I’ve argued before, the Church-Turing thesis is a thesis and not a theorem or even conjecture of mathematics, and as such I would not consider it as falling under purely mathematical reasoning.

Post and Cognitivism

Emil Post was probably the first to recognize the importance of the Church-Turing thesis as a radically different statement that should not be simply absorbed as a fact of mathematics. In footnote 8 of his short 1936 paper, Post noted:

Actually the work already done by Church and others carries [the identification of effective calculability with recursiveness] considerably beyond the working hypothesis stage. But to mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematicizing power of Home Sapiens has been made and blinds us to the need of its continual verification.

Post’s goal was to explore the Church-Turing thesis and develop a formulation of the computable whose purpose “is not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity” (Post, 1936). In other words, he was exploring the psychological structure of our apparatus of perception; in modern terminology, Post was probably the first cognitivist.

For the purposes of this article, however, I will depart from modern cognitivism. In particular, a modern cognitivist holds two main beliefs: (1) cognition consists of internal mental representations that are manipulated algorithmically, and (2) that psychology can (in principle) be explained from an experimental and physicalist perspective. I will hold on to the first, but the second belief would make the cognitivist Church-Turing thesis a consequence of the physicalist view. If we think all of the mind can be fully explained in terms of physical processes and we believe that physical processes are computable by a Turing machine then all processes of the mind are also computable by a Turing machine. This would not satisfy Kant, because if the Church-Turing thesis is a property of our apparatus of perception then the fact that the world appears to confirm to it is not a property of the world but of our sense organs. As such, the rightful source of our confidence in the CT-thesis is not the observation of the apparent world but transcendental deduction of the same kind that led Kant to conclude that space is an inescapable property of our way of sensing.

This is the position that I would like to advance as Post’s variant of the Church-Turing thesis; the belief that the the Turing Machine or other equivalent forms of computation capture what is thinkable by us, and express the restriction of our finite understanding. This is my preferred variant of the thesis because it seems less arrogant to assume a restriction on our process of cognition than to project that untestable restriction either onto the external sensible or intelligible worlds. Of course, this is only an upper bound, and we can further refine as we shift from computability to complexity theory and ask what complexity class is mostly closely associated with the human mind.

Post’s variant of the Church-Turing thesis also allows us to capture the idea of our finite understanding, and even allows us to return to the two worlds of the Inaugural Dissertation. One of the reason Kant abandoned the great power of understanding that he allowed in his earlier work was because perfect understanding of the intelligible world seemed inaccessible. However, to me it seems that any argument for an external sensible world also carried over to an argument for an external intelligible world. Further, thanks to Godel we know that even if we postulate an external objective mathematics or intelligible world, we cannot capture the totality of that world with the finite understanding of our subjective mathematics. Thus, Post’s variant of the CT-thesis allows us to bring back the two worlds of the Inaugural Dissertation, with us having access only to a finite understanding of each. This appearance is guided by our senses in one case and intuition in the other, and constrained by the form of the computable in both.

References

Copeland, B.J., & Shagrir, O. (2013). Turing versus Godel on computability and the mind. In Copeland, B.J., Posy, C.J., & Shagrir, O. (Eds.), Computability: Turing, Gödel, Church, and Beyond. MIT Press.

Gandy, R. (1980). Church’s thesis and principles for mechanisms. Studies in Logic and the Foundations of Mathematics (101), 123-148.

Hartz, G.A., & Cover, J.A. (1988). Space and Time in the Leibnizian Metaphysic. Nous, 22: 493-519.

Hintikka, J. (1967). Kant on the mathematical methods. Monist, 51: 352-375.

Kant, I. (1770). Concerning the Form and Principles of the Sensible and Intelligible World.

Kant, I. (1787). Critique of Pure Reason. Second Edition.

Lennon, T.M. and Dea, S. (2012). Continental Rationalism. The Stanford Encyclopedia of Philosophy.

Post, E.L. (1936). Finite combinatory processes — formulation 1. Journal of Symbolic Logic, 1 (3), 103-105

Rohlf, M. (2010), Immanuel Kant. The Stanford Encyclopedia of Philosophy.