# Pairing tools and problems: a lesson from the methods of mathematics and the Entscheidungsproblem

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.

### References

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

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.

### 21 Responses to Pairing tools and problems: a lesson from the methods of mathematics and the Entscheidungsproblem

1. Jon Awbrey says:

I remember having a similar discussion a number of times in the early days of object-oriented programming, or at least when the “fadding crowd” first latched onto it.

We might picture the dyadic relation between Objects and Processes as a rectangular matrix with a entry of $1$ indicating where Process $p, q, r, s, t, u, \ldots$ has meaningful application to Object $a, b, c, d, e, f, \ldots$

$\begin{array}{c|ccccccc} \cdot & p & q & r & s & t & u & \ldots \\ \hline \\ a & & & 1 & 1 & & & \ldots \\ b & & 1 & 1 & 1 & & & \ldots \\ c & 1 & 1 & 1 & 1 & 1 & 1 & \ldots \\ d & & 1 & 1 & 1 & 1 & & \ldots \\ e & & & 1 & 1 & 1 & & \ldots \\ f & & & 1 & 1 & & & \ldots \\ \ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots \end{array}$

Then the process orientation amounts to slicing the matrix along columns while the object orientation amounts to slicing it along rows.

But a more general orientation might consider the possibility that the tuples naturally cluster in different ways, partitioning the space into shapes more general than vertical or horizontal stripes.

2. Sergio Graziosi says:

Artem, I’m struggling with this one because each time I read your post I’m tempted to conclude that you are somehow over-complicating your main point. This is a danger you are clearly well-aware of, so I’m inclined to conclude that I’m probably missing your point.

I’ll summarise what I think you are saying below, hopefully clearing things up (validating my hunch or exposing what I’m missing).

To me, your are saying that interesting problems are the ones that allow to expand existing theories while trying to solve the problem.

Expanded a little bit, this becomes:
– All problems come with some theoretical assumptions.
– Well developed theories (conceptual frameworks) allow for well-formed questions to be asked (problems).
– Conversely, “folk” or otherwise underdeveloped theories frequently allow to ask badly formed questions (questions that do not allow for correct answers, not even in theory; these questions are possible because the theory is underdeveloped).
– As conceptual frameworks develop, some questions are brushed aside as ill-conceived.
– At the same time, answers to some other (well formed) questions become trivial (e.g. not interesting).
– Hence, interesting questions are those that expose the current limits of a given theoretical framework and allow to develop it (our tool) while looking for an answer.
I would add: concentrating on “good questions” as defined above allows to get two results (finding an answer, expanding the usefulness of a theory) with one effort.

Given your self-confessed “theorist ethos”, this isn’t a surprise: what else would you do? [your approach maximises your own utility; once we know your chosen “mission statement” it is the natural approach]

On the other hand, other people may not have the option: for example, my day job is about evidence synthesis (mostly for policy-making). In this business the questions are chosen elsewhere and arrive with funds attached. This generates a very understandable mainstream drive towards plain old “picking the right tool”. The drive towards expanding the accuracy, applicability and power of existing tools is indeed present under the surface, and is counterbalanced by the drive towards re-defining the questions we receive, so to make them fit our tools. In this context, the primary and consequent drives are swapped around, with some subtle differences on priorities (but surely everyone appreciates when they manage to produce good answers and at the same time devise methodological developments and/or theoretical advancements).

As I’ve said, this all looks rather trivial to me, generating the natural intuition: I must be missing something…

PS I’m also a bit suspicious of the tooltheory equivalence. Am I wrongly reading it into your text?

• your approach maximises your own utility; once we know your chosen “mission statement” it is the natural approach

I completely agree, it would be a bigger problem if they didn’t align, no? However, by making this post I am also hoping to win people over to both my mission statement and to this approach. I also hope that I am not saying that this is the only way or the best was to “do science” or “do theorist-ing”, I am more trying to say: “this is my way — or the ideal to which I aspire — and I hope that more will join me”.

You point out that you “may not have [this] option” and in that case my post might not be targeting you (although maybe it still is). However, I know people who do have this option and freedoms similar to my own but still stick to the “best tool for the job” mentality. To make matters worse, they often also view the “best tool for the job” mentality as the only acceptable one or the superior one. I fear that this can be especially problematic when those with power (such as the policy-maker forcing a question on you, or the funding agency) hold such dogma.

Your summary of my points is largely fair. The only point where I would disagree, or clarify, is that you paint folk-theories more negatively than how I had hoped to. Folk theories are essential for giving questions meaning and projects purpose; purely endogenous questions are usually purely pointless and the tension is striking a balance.

One other point that I would like to touch on — and I am not sure if I have or not in the OP — is that when you have a question from a folk-theory that you cannot be sure is well-posed then the concept of the “best tool for the job” becomes moot. If the question is non-nonsensical (or trivial) then how can you have a “best” tool for answering it? In such cases, the choice of tool becomes rather an exercise in fashion. Sometimes this can be bad, but sometimes it can lead to the development of many ‘school of thought’ that together enrich our world; of course, in such settings it is important that no single school asserts an unjustified “epistemological supremacy” over the others. In such cases it is important to maintain plurality.

In such cases, the field also develops in a much less cumulative way than fields like mathematics or (to a lesser extent) physics. Some view this as “bad” and use a loaded word like “progressive” instead of “cumulative”. I don’t want to suggest that I hold this negative judgement, at least not anymore (logical-positivist past-Artem probably did).

Finally, to come back to the policy-maker imposed questions. Here, I think that — surprise, surprise — computer science (broadly construed) can also help. Unfortunately, it is a part of computer science I know nothing about: software engineering. As far as I understand, a big practical concern for people that think about running software teams is how to interact with the client, and how to “work them” into coming up with well-formed and actually-useful-to-them goals for the project they are assigning you. As far as I understand, you can’t simply let them ask them what they want, since they won’t know what they want or reply with things that they think they want — because they don’t understand how the relevant software works — but don’t actually want or need. The art form of managing this could probably come in useful for modelers.

• Sergio Graziosi says:

Artem,
Glad I didn’t badly misinterpret your main point. The bubbles we inhabit are very different and it’s always stimulating to glimpse into yours.

Folk theories are essential for giving questions meaning and projects purpose; purely endogenous questions are usually purely pointless and the tension is striking a balance.

Agreed, I’ve glossed over this side in my summary: I’m also firmly convinced that in the end what drives the supply of interesting questions is a form of (folk) intuition. Given one broad view of the world, and/or an overarching epistemological approach, certain problems will pop-out as particularly tricky, and the trickiness makes them interesting! Some of these problems are shared between large portions of humanity, and we call them folk, some others pop out of specialist approaches, and ultimately generate/sustain the plurality you mention.

Thinking about plural and frequently irreconcilable approaches, I’m slowly realising how my own approach generates its own tension:
As you know, on one side I strive to welcome plurality, both in terms of intellectual growth, research organisation, and in terms of society as a whole. Because every single approach has to entail it’s own self-imposed limitations, it is necessary to always promote the proliferation of approaches, and cover each-other’s blind spots.
On the other side, I can’t escape the allure of coherence and really get excited when I sniff a way to bring together two theories into a new, encompassing view (with the precise intention of then claiming epistemological supremacy, argh!). Thus, I’m actively trying to reduce plurality! D’oh! Depravity at its best.
You could say that in this context the effort to maximise coherence undermines itself. Is this the twisted counterpart of straightforward interdisciplinitis? ;-)

As an amateur theorist I like to think that this tension can be managed by focussing on exploring the limitations of the different approaches: what’s wrong with learning to recognise and to progressively pin-down the weak spots of any given theory? This could offer a way forward, but I fear that incoherence lurks just the same: ex-hypothesis also this approach has to have it’s own weaknesses and self-imposed limitations.

Funny that you mention software engineering, the need to produce sensible specifications, and the context of policy making. You more or less mentioned all the things that make my day job interesting… I think the analogy with a client that asks for a new software, and doesn’t really understand the problem that the software should address, is spot-on. I know nothing of the theory of how to make the client’s expectations converge towards some achievable goal, but I know that in practice an iterative process seems to work. It works by facilitating the emergence of acceptable compromises, I suspect.

• To revive this thread a year later:

Thinking about plural and frequently irreconcilable approaches, I’m slowly realising how my own approach generates its own tension

You then go on to outline two horns: (1) you like plurality, (2) you want to merge views into coherent wholes. I don’t think these are actually at odds with each other. Plurality, at least for me, is not about the endless proliferation of views for the sake of more views; it is about respecting views and taking them on their own terms. For your second point, you wrote that:

I can’t escape the allure of coherence and really get excited when I sniff a way to bring together two theories into a new, encompassing view (with the precise intention of then claiming epistemological supremacy, argh!).

If you justified your unification from within each of the two theories — thus maybe with two different justifications — that you ended up unifying then I think that you have not done an injustice to plurality. I think that an injustice was only committed if you used an authority that neither (or at least not one) of the prior theories recognizes as legitimate. The worst travesty is when a certain view that people have developed carefully over a long tradition is simply dismissed out of hand. But given our finite time and energy, sometimes as individuals we have to commit this crime. But do we have to do this as a society?

I know nothing of the theory of how to make the client’s expectations converge towards some achievable goal, but I know that in practice an iterative process seems to work. It works by facilitating the emergence of acceptable compromises, I suspect.

Fundamentally, I think that this iterative process of acceptable compromises is just inquiry. And I think that this highlights the importance of viewing truth/knowledge/etc as processes and not merely as states to achieve.

3. gabogoren says: