Pairing tools and problems: a lesson from the methods of mathematics and the Entscheidungsproblem
March 16, 2015 12 Comments
Three weeks ago it was my lot to present at the weekly integrated mathematical oncology department meeting. Given the informal setting, I decided to grab one gimmick and run with it. I titled my talk: ‘2’. It was an overview of two recent projects that I’ve been working on: double public goods for acid mediated tumour invasion, and edge
effects in game theoretic dynamics of solid tumours. For the former, I considered two approximations: the limit as the number n of interaction partners is large and the limit as n = 1 — so there are two interacting parties. But the numerology didn’t stop there, my real goal was to highlight a duality between tools or techniques and the problems we apply them to or domains we use them in. As is popular at the IMO, the talk was live-tweeted with many unflattering photos and this great paraphrase (or was it a quote?) by David Basanta from my presentation’s opening:
Since I was rather sleep deprived from preparing my slides, I am not sure what I said exactly but I meant to say something like the following:
I don’t subscribe to the perspective that we should pick the best tool for the job. Instead, I try to pick the best tuple of job and tool given my personal tastes, competences, and intuitions. In doing so, I aim to push the tool slightly beyond its prior borders — usually with an incremental technical improvement — while also exploring a variant perspective — but hopefully still grounded in the local language — on some domain of interest. The job and tool march hand in hand.
In this post, I want to unpack this principle and follow it a little deeper into the philosophy of science. In the process, I will touch on the differences between endogenous and exogenous questions. I will draw some examples from my own work, by will rely primarily on methodological inspiration from pure math and the early days of theoretical computer science.
Boundary between tools and problem-domains
To begin, it is important to notice that the tool versus problem-domain distinction is fluid and often arbitrary. One person’s tool is another person’s domain. Let’s look at the study of living things: nothing in biology makes sense — as Dobzhansky (1973) reminds us — except in the light of evolution; so biology is our domain and evolution our tool. But, how does evolution proceed? Wright (1932) suggests that it is a walk along a fitness landscape. Evolution is our domain and fitness landscapes are our tool. There are a lot of different fitness landscapes, can we say something about their structure by making them our domain? Wiser, Ribeck, and Lenski (2013) might use the long term evolution experiment — an experimental tool — to tell us that convergence in static fitness landscapes is slow or I might use the simplex algorithm (Kaznatcheev, 2013) — a theoretical tool — to explain how we can see such slow convergence to a local-fitness peak even without reciprocal sign epistasis. Matousek & Szabo (2006) could then use the tool of the probabilistic method in combinatorics to inform us about the problem domain of convergence rates for simplex algorithms. In this paragraph, we see 4 levels of nesting of tools becoming domains; I encourage you to come up with other examples.
Of course, the above is only a disclaimer and not an argument for my principle. One can be mindful of the fluidity of tools and still think of us as picking a problem-domain first and then selecting the best tool for that domain. Even if the problem is arbitrary, it is prior, and one should only pick the tool once they know what question they are asking. This position is the real target of my principle and this post.
Pseudo-questions and the implicit explanatory framework
There are sentences that are grammatically well formed and end in question marks but aren’t quite questions — to shamelessly appropriate from Chomsky (1957) — “How furiously do the colorless green ideas sleep?” On the surface that might even be a quantitative empirical question; maybe I’ve already built a furiositometer. But in posing the question, I have built up a background framework of auxiliary hypotheses, with much of them clearly nonsensical. Even if I have a furiositometer, what could it possibly tell me about ideas that are colorless and green?
Unfortunately, not all pseudo-questions are so clearly marked.
“Does the soul reside in the heart or the head?” was a perfectly well-formed question to the ancients. It even seemed empirical: removing either had a pretty drastic effect on the soul’s ability to control the body. Both had a reductionist basis: the heart and the brain had an intricate network of connections to the rest of the body. You could argue that this is an issue of translation; instead of ‘soul’ I should have instead written ‘mind’. In fact, I secretly hope that your reaction was this because I think the real problem in that question was the assumptions underlying ‘reside in’, or maybe — as Dan Nichol pointed out in conversation — the false dichotomy between head and heart, or maybe the idea of ‘mind’ or ‘soul’ as a unity. We could — and philosophers of mind do — spend volumes uncovering all the (unjustified and arbitrary) auxiliary hypotheses implicit in that question.
My point is that all questions or problems drag with them the baggage of an explanatory framework. This point is not particularly novel, for example it can be seen within the Duhem-Quine thesis. The Durhem-Quine thesis states that it is impossible to empirically test an isolated scientific hypothesis because any hypothesis requires background assumptions. My intellectual debt to Duhem-Quine is why I use the technical term of ‘auxiliary hypothesis’. Except, I am not concerned with trying to falsify a hypothesis, but with testing a question for being well-posed. I am also not restricting this to empirical statements, but think the importance of context applies to all questions or problems. Here, I am also structuring my thought in terms of Quine’s metaphor of the Web of Belief, where any given statement is situated within and given meaning by its relationship to our other beliefs. This web can be individual, or communal and different parts of it can differ in their explicitness and formality.
Continuum of endogenous to exogenous questions
When you increase the formality of your beliefs by being conscious of your tools and their limitations — plus the framework they are embedded in — while you ask your question then you can become aware of more of these auxiliary assumptions. However, asking a question without being mindful of the tool you will be using to answer it will not free you from assumptions, instead you will (often) just make these assumptions harder to find. More importantly, when you try to ask a question without an explicit theoretical framework what you will typically end up doing is substituting in a folk-theory as your basis instead of a scientific theory or careful philosophical framework. For me, this is the difference between endogenous and exogenous questions.
I will call a question endogenous to a field of critical thought — be it a science, math, or philosophy — if it is motivated by the existing tools developed for the field, or slight extensions of them. Given that these tools have undergone critical scrutiny, they often have formal or other well understood representations, and it is relatively clear what we can expect answers to look like in such a framework. On the opposite end of the spectrum: I will call a question exogenous to a field of critical thought if motivated by frameworks or concerns external to the field. Usually, such an external motivating framework is accepted uncritically with the most common culprits being the unarticulated ‘intuitive’ and ‘natural’ folk theories forced on us by our everyday experiences; think of folk-psychology or folk-physics. Although intuitively grasped, these frameworks often don’t have formal or clearly understood representations. In fact, understanding the structure of these intuitive humans frameworks is often an active problem-domain for anthropologists, philosophers, psychologists, and sociologists.
Not all folk theories have the same grip on us. For example, I would guess that folk-mathematics has a much weaker grasp on us than folk-physics or folk-psychology, especially if we are talking about mathematics where our untrained intuitions are weakest — that is the branches that are not near geometry. Between the other two folk theories, I would — and will, in a future post — argue that folk-physics has a strong but still much weaker grip on us than folk-psychology. Although throwing stones and judging gravity is important to us, it is not nearly as important as judging and predicting the (often subtle) behavioral cues of other people. Just like we can try to learn the structure of our intuitive human frameworks, we can also try to learn why some have a stronger grip on us. In the case of physics vs psychology, I expect an evolutionary reason via the social brain hypothesis (Dunbar, 1993; 1998; for a comparison to other hypotheses, see here). A frog probably needs to judge throwing its tongue as well as we need to judge throwing stones, and given its great jumping probably needs a much better intuitive understanding of gravity than we do. One of the main things that sets humans apart from other animals is the richness our intuitive understanding of our social structures and our individual place within this organization. I expect this richer understanding to translate into a harder to escape folk-theory.
Obviously, these the endogenous versus exogenous distinction is not two strict categories; any specific question or problem lays on a continuum between these two extremes.
Even mathematical questions are not complete endogenous
I suspect that no process of inquiry has completely endogenous questions, although pure math seems to be the most self-generating and the most divorced from folk-theory. But even a mathematician inadvertently ends up prioritizing endogenous questions that are in some way ‘closer’ to ones that are imposed on her by the partially exogenous pressure of intuition. She doesn’t simply write down a formal system and start listing all possible deductions from it. In fact, deduction from a formal system is almost never done in practice. Usually, from her years of training, the mathematician’s intuition is tuned to the point that they imagine the outline of a theorem that they want to and think that they can prove — or they might be targeting an existing conjecture, an outline seen by earlier mathematicians — and then try to find a rationalization for that theorem, a deduction leading from statements already accepted by the community to the ones that is not yet accepted. In the process, she might end up changing her goals slightly by tightening or generalizing the conditions or conclusions. Further, the intuitions that shape her target are themselves shaped by her experience with her formal framework and thus specifically take into account the tools that she expects to be used to answer the question. “An important criterion for … [an] interesting conjecture” — writes Matthew Emerton on math.SE — is “fitting well within the known framework of the subject, while simultaneously extending this framework in a new and interesting way”. In other words, I stole my principle of pairing problems with tools from what mathematicians consider to be a good conjecture or open problem.
However, even when mathematicians take these careful steps to form clear questions with well understood theoretical frameworks for their auxiliary hypotheses — the ideal of an endogenous question — they can be led into dead ends by exogenous concerns; the most dangerous of which is often things like wishful thinking. A classic example of this would be Hilbert’s Entscheidungsproblem. A problem that arose, ironically enough, in trying to formalize the very method of mathematics we are borrowing from. In partical, Hilbert’s formalists were trying to show that all of mathematical reasoning could be replaced by the deduction from axioms that I dismissed above. The formalists failed, but left us a history to learn from.
In the popular anachronistic retelling that we typically hear in introductory computer science courses, the Entscheidungsproblem is the innocent question: “is there an algorithm that determines for each logical expression if it is valid or satisfiable?” Unfortunately, this question was asked only after Church and Turing (and Post) gave the negative answer. But when Hilbert and Ackermann stated this problem in the Grundzüge der Theoretischen Logik in 1928, they could not envision anything like undecidability as a possibility. “What is the procedure”, they asked, “that determines for each logical expression for which domains it is valid or satisfiable?”. It was up to Church, Post, and Turing to formalize the notion of algorithm to replace the exogenous idea of ‘procedure’, and then courageously suppose, emboldened by Godel, that the answers is not a procedure but “your question was malformed, Herr Prof. Dr. Hilbert; no procedure exists to solve the Entscheidungsproblem”. Finally, although the undecidability result was exciting, the real reason that these papers are remembered — and why Turing (1936) is singled out above Church’s earlier work — is that they formalized our exogenous notion of procedure and clarified the formal framework for understanding human’s computation.
Although Hilbert’s was question asked in a misleading way, it was close enough to a well understood framework and the tools of mathematical logic that a clarification was possible. That is why we remember the clearly stated problem as Hilbert’s and not as Leibniz’s. Although the latter flirted with a similar intuitive problem after successfully constructing the Stepped Reckoner, a calculating machine, in the late seventeenth century (Davis, 2000). However, Leibniz could not ask his question because he could not find a good problem-tool pair that made the question sufficiently clear. Instead, over 200 years later, Hilbert found the problem and tool pair, and Turing found the slight extension of the tool and corresponding change to the problem to provide an answer and leave us with an increasingly useful framework.
Note, that I am not saying that we should pass over in silence all questions for which we don’t have a formal theoretical framework to justify a reasonable answer. Endogenous questions are great if we are doing inquiry for the sake of inquiring — as is the goal in pure mathematics — but there is no reason to expect a (close to) purely endogenous process to lead us toward questions that resemble ones that we wanted to answer before we started inquiring. The vast majority of theorems discovered and tools developed in pure mathematics never leave the field, and I suspect the few that do manage to leave do so because mathematics is an important tool in the kit of a good theorist; as the theorist searches for new pairs of tools and questions, they inevitably find a problem-domain where the new pure math tools they know can be applied. In fact, if we trace our conceptual metaphors closely, we will find that all our theories are eventually grounded in exogenous considerations of folk theories forced on us by our embodied existence. Thus, crafting a good problem-tool pair is a balancing act, we need enough formal theory for the question to have a precise meaning but enough folk theory for the question to be meaningful to us.
Finding a good pair can be very difficult, often — maybe even hopefully — more difficult than proceeding to solve the resulting question. Good luck with the search for your tuple, dear reader. My biggest advice to the a theoretician in any field of science (or inquiry more broadly) and more importantly to the domain-less theorist is the same as the advice of Pólya (1945) to mathematicians: “If you can’t solve a problem, then there is an easier problem you can solve: find it.” Don’t modify just your tools in the search for the mythical ‘best tool for the job’ but also change the problem.
Chomsky, N. (1957). Syntactic Structures. The Hague/Paris: Mouton.
Davis, M. (2000). Engines of Logic. London: W.W. Norton & Compan.
Dobzhansky, T. (1973). Nothing in Biology Makes Sense Except in the Light of Evolution, American Biology Teacher 35(3): 125–129.
Dunbar, R.I.M. (1993). Coevolution of neocortical size, group size and language in humans. Behavioural and Brain Sciences, 16: 681-735.
Dunbar, R.I.M. (1998). The social brain hypothesis. Evol. Anthropol., 6: 178–190.
Hilbert, D. & Ackermann, W. (1928). Grundzüge der Theoretischen Logik. Berlin: Julius Springer.
Kaznatcheev, A. (2013). Complexity of evolutionary equilibria in static fitness landscapes. arXiv arXiv: 1308.5094v1
Pólya, G. (1945). How to Solve It. Garden City, NY: Doubleday.
Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2(42): 230–65.
Wiser, M. J., Ribeck, N., & Lenski, R. E. (2013). Long-term dynamics of adaptation in asexual populations. Science, 342(6164): 1364-1367.
Wright, S. (1932). The roles of mutation, inbreeding, crossbreeding, and selection in evolution. Proceedings of the Sixth International Congress of Genetics, 356-366