At various times, I have blogged a series of posts as I read through a book, often en route to writing a review. One of first books to get this treatment was the collection of articles Church’s Thesis After 70 Years edited by Adam Olszewski et al. This was a very mixed bag, as is often the way with such collections. But some pieces stood out as worth thinking about. Here’s one (which I initially posted about in 2007, but returned to a bit later when we read it one Thursday in the Logic Seminar.
Stewart Shapiro, “Computability, Proof, and Open-Texture” (January 18, 2008)
Let me say straight away that it is a very nice paper, written with Stewart Shapiro’s characteristic clarity and good sense.
Leaving aside all considerations about physical computability, there are at least three ideas in play in the vicinity of the Church-Turing Thesis. Or betters there is first a cluster of inchoate, informal, open-ended, vaguely circumscribed ideas of computability, shaped by some paradigm examples of everyday computational exercises. Then second there is the semi-technical idea of effective computability (with quite a carefully circumscribed though still informal definition, as given in various texts, such as Hartley Rogers’ classic). Then thirdly there is the idea of Turing computability (and along with that, of course, the other provability equivalent characterizations of computability as recursiveness, etc.).
It will be agreed on all sides that our original inchoate, informal, open-ended ideas could and can be sharpened up in various ways. Hence, the notion of effective computability takes some strands in inchoate notion and refines and radically idealizes them in certain ways (e.g. by abstracting from practical considerations of the amount of time or memory resources a computation would use). But there are other notions, e.g. of feasible computability, that can also be distilled out. Or notions of what is computable by a physically realisable set-up in this or other worlds. It isn’t that the notion of effective computability is — so to speak — the only clear concept waiting to be revealed as the initial fog clears.
So I think that Shapiro’s rather Lakatosian comments in his paper about how concepts get refined and developed and sharpened in mathematical practice are all well-taken, as comments about how we get from our initial inchoate preformal ideas to, in particular, the semi-technical notion of effective computability. And yes, I agree, it is important to emphasize is that we do indeed need to do some significant pre-processing of our initial inchoate notion of computability before we arrive at a notion, effective computability, that can reasonably be asserted to be co-extensive with Turing computability. After all, ‘computable’ means, roughly, ‘can be computed’: but ‘can’ relative to what constraints? Is the Ackermann function computable (even though for small arguments its value has more digits than particles in the known universe)? Our agreed judgements about elementary examples of common-or-garden computation don’t settle the answer to exotic questions like that. And there is an element of decision — guided of course by the desire for interesting, fruitful concepts — in the way we refine the inchoate notion of computability to arrive at the idea of effective computability (e.g. we abstract entirely away from consideration of the number of steps needed to execute an effective step-by-step computation, while insisting that we keep a low bound on the intelligence required to execute each particular step). Shapiro writes very well about this kind of exercise of reducing the amount of ‘open texture’ in an inchoate informal concept (or concept-cluster) and arriving at something more sharply bounded.
But another question arises about the relation between the semi-technical notion of effective computability, once we’ve got there, and the notion of Turing computability. Now, Shapiro writes as if the move onwards from the semi-technical notion is (as it were) just more of the same. In other words, the same Lakatosian dynamic (rational conceptual development under the pressure of proof-development) is at work in first getting from the original inchoate notion of computability to the notion of effective computability, as in then going on eventually to refine out the notion of Turing computability. Well, that’s a good picture of what is going on at the conceptual level. But Shapiro seems to assume that this conceptual refinement goes along with a narrowing of extension (in getting our concepts sharper, we are drawing tighter boundaries). But that doesn’t obviously follow. An alternative picture is that once we have got as far as the notion of effective computable functions, we do have a notion which, though informal, is subject to sufficient constraints to ensure that it does indeed have a determinate extension (the class of Turing-computable functions). We can go on to say more about that extension, in coming up with various co-extensive technical notions of computability, but still the semi-technical notion of effective computability does enough for fix the class of functions we are talking about. For some exploration of the latter view, see for example Robert Black’s 2000 Philosophia Mathematica paper.
So a key issue here is this: is further refinement of “open texture” in the notion of effective computability required to determine a clear extension? Shapiro seems to think so. But looking at his paper, it is in fact difficult to discern any argument for supposing that things go his way. He is good and clear about how the notion of effective computability gets developed. But he seems to assume, rather than argue, that we need more of the same kind of conceptual development before we are entitled to settle the Turing computable/the recursive as a canonically privileged class of effectively computable function. But supposing that these are moves of the same kind is in fact exactly the point at issue in some recent debates. And that point, to my mind, isn’t sufficiently directly addressed by Shapiro in his last couple of pages to make his discussion of these matters entirely convincing.