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

KantPostOne 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.


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.


About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

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

  1. Jon Awbrey says:

    Love This❣

    I spent one of my parallel lives through the entire decade of the 1980s writing a single program, beginning in Lisp on a monster mainframe and porting over to Pascal on various vintages of various vendors’ microcomputers. The hardest part of the nut I had to hack was the problem of integrating what programmers would call data-driven versus concept-driven styles of processing and philosophy students would recognize as empiricist versus rationalist approaches to knowledge. I did manage to get a Masters in psych out of the work, applying the resulting program to “protocol analysis” and the exploratory analysis of sequential observation data in a family interaction research study.

    Susan Awbrey and I wrote up a guidebook that documented the philosophical sources of the program. Aristotle and Peirce figured prominently and there was in addition the work of Gerald Edelman on neural embryology. The data structures that I crafted for my program bear some analogy to the “growth cones” that figure in neural development.

    Theme One Program • User Guide

    Edelman, Gerald M. (1988), Topobiology : An Introduction to Molecular Embryology, Basic Books, New York, NY.

  2. Jon Awbrey says:

    Re: “any function [realizable] by a physical [process] is computable by a Turing machine”

    I modified this assertion to avoid begging the same questions on both sides of the equation.

    This is where the crux lies. And it really goes back to Aristotle’s idea that knowledge is of generals or universals not individuals (meaning utterly unique, idiosyncratic, irreproducible haecceities or hapax legomena). We inherit the same idea in computation when we say that a computational problem is a set not a singular instance, and that finite sets count the same as one.

    In other words, we have to distinguish physis, whatever happens in the universe, from physics, our knowledge (scientia) of same.

    Things that happen one time only, a finite number of times being the same as one, are neither a phenomenon nor a problem for science to handle.

    To adopt scientific method is to accept a voluntary limitation. It is the limit that makes it a method.

    To adopt computational method is to accept a voluntary limitation. The question that remains at this point is whether the two limits, reproducible events and computable sets, are the same.

    • I think this comment and the discussion it is suggestively pointing to might find a better home on my earlier post about the physicalist variant of the CT-thesis. There I address the same begging the same question on both sides of the question issue by defining the physicalist version as:

      the statistics of measurement for any repeatable physical process can be approximated arbitrarily well by a Turing machine

      I do like the idea of examine how the two limits of reproducible evens and computable sets interact. I suspect it is possible to show that the basic assumptions we usually take for granted to do science (causal order, some “working man”‘s induction, categorization, finite data sets, maybe a few other things) are enough to show that everything that pops out is computable. However, that doesn’t really address the ontological question that I sketched toward the end of this post all that much (not that the question needs to be addressed, or that I expect it to have a ‘solution’), is this computability a property of our senses? Is it a property of matters of fact? Can we have workable theories that are more than Turing computable in some useful sense?

      • Jon Awbrey says:

        I was trying avoid the particulars of any one variant and make it over into the sort of ontological thesis that you hear people suggesting when they say that the universe IS (1) a finite automaton, (2) a whatever-bounded automaton, (3) a turing machine, etc.

        I am saying that when we opt for scientific method we have abandoned hope, to coin a phrase, of being sure what the devil the universe IS, and accepted a limitation to what is possibly the proper portion of its phenomena that indefinitely repeat, however quasi-periodically or ultimately periodic that may be.

        Throw in approximation and all bets are off … that’s another (billiard) ball game …

  3. Pingback: Transcendental idealism and Post’s varian...

  4. derek says:

    wonder what a Buddhist computing theory would be, space is never a problem to be investigated, it is just an illusion of the self etc etc maybe binary would be laugh at when quantum theory really requires “3”

  5. Pingback: Should we be astonished by the Principle of “Least” Action? | Theory, Evolution, and Games Group

  6. Pingback: Limits of prediction: stochasticity, chaos, and computation | Theory, Evolution, and Games Group

  7. Pingback: Cataloging a year of blogging: the philosophical turn | Theory, Evolution, and Games Group

  8. Pingback: An update | Theory, Evolution, and Games Group

  9. Pingback: Argument is the midwife of ideas (and other metaphors) | Theory, Evolution, and Games Group

  10. Pingback: Alan Turing and science through the algorithmic lens » Heidelberg Laureate Forum » SciLogs - Wissenschaftsblogs

  11. Pingback: Antoni Gaudi and learning algorithms from Nature | Theory, Evolution, and Games Group

  12. Pingback: Cataloging a year of blogging: complexity in evolution, general models, and philosophy | Theory, Evolution, and Games Group

  13. Pingback: Algorithmic lens as Alan Turing’s wider impact | Theory, Evolution, and Games Group

  14. Pingback: Hobbes on knowledge & computer simulations of evolution | Theory, Evolution, and Games Group

  15. Pingback: Plato and the working mathematician on Truth and discourse | Theory, Evolution, and Games Group

  16. Pingback: Reductionism: to computer science from philosophy | Theory, Evolution, and Games Group

  17. Pingback: From perpetual motion machines to the Entscheidungsproblem | Theory, Evolution, and Games Group

  18. JV 2000 says:

    I’m looking at this topic now within the context of trying to establish the grounds for (some type of) quantum metaphysics.

    It appears to me (as a MS in CS) that what Kant does in his Critique is to create the business rules, the logic, for a somewhat limited version of a Turing Machine that computes via propositional logic (true-false). It is consistent and fully coherent in this sense, and can be replicated (now) with a machine, including the cognitive elements of learning interestingly (ML around image processing for example which is now ubiquitous more or less in captcha tech for example).

    If the test for “objective validity” is relaxed to be effectively computable (which implies a consistent set of logical assertions or statements regarding a certain set of data and a final set of states for such processing, ie a Turing Machine), which i think is fair given what Kant is trying to achieve (a level of certainty that applies for all circumstances and situations regarding cognition), then Kant’s epistemological framework expands to align with computability does it not? If the equivalence between his model that he puts forth in the Critique of Pure Reason and a (specific type) of Turing Machine.

    If this can be done, this equivalence, it would seem to me that it would allow for an expanded application of Kant’s epistemological framework beyond simply subjective cognition, ie more applicability from what it says about the world in and of itself – as agreed upon by all sentient beings (humans and AI in this case being defined as sentient, ie capable of cognitive processing and analysis) rather than just what can be said about the world as it “appears” to us.


    • One can certainly take a physicalist view of the CT-thesis, and I think this is currently the most popular stance. From this perspective, you can say things about the world itself (since it is just some kind of computer). But I don’t really see what it has to do with Kant.

      For me, AI has nothing interesting to say about the Kantian view. One simply defines the phenomenal world as the world perceived and discussed by your epistemic community. AI might (and to some extent already does… but so does an abacus or any other cognitive tool) extend that community to be broader. But the point of Post’s variant for me is that communicable theories of the phenomenal world are by definition computable things. We cannot share between ourselves something beyond this, and so anything else in the noumenal world beyond this will be unintelligible (I’m sure this can be linked to some theology if one wanted to, as I joked on twitter).

      Where I think this does have a potential interesting connection to quantum is if we take Post’s variant of a strong CT-thesis. In other words, we equate what is thinkable not with what is computable but what is efficiently computable by a classic computer. This opens the door for some interesting things if we believe (as we should) that BQP is strictly more powerful than BPP: this means that we can run and predict the outcome of physical processes that we fundamentally cannot understand. This would be a fun cstheoretic way of making sense of what Bohr was after when he motioned at the tension we have of reconciling quantum mechanics with the conceptions of classic physics (like position and momentum) that sit well in our minds.

      I don’t know if I believe the idea that I suggest in the third paragraph. But it is certainly fun to think about. Sorry that I didn’t really stay on the topic of your comment but those are the thoughts that sprung to mind. Thank you!

      • JV 2000 says:

        Interesting. Thx for the response. Makes sense. What struck me when reading Kants Critique is thus basic affinity between his epistemological position and not computability generally but the likeness of his attempts to bound knowledge within logical constraints (analytic and synthetic judgments essentially) that, as far as I can tell at least, should be fully describable by a classical computer, which (if true) can provide an empirical basis for his epistemology which (if true) should provide for an equivalence between his epistemology and computability more generally.

        If this analogy holds you end up with Categories as sort of an embodied firmware, as a priori synthetic judgments yes but not so much transcendental but more rooted in the human (and animal) form.

        I haven’t fully fleshed the idea out yet but this is the gist of it. Or the core part of it at least.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: