Church’s Thesis 7: Physical computability

As light relief from tripos marking, back to commenting on two more papers in the Olszewski collection: “Church’s Thesis and physical computation” by Hartmut Fitz, and “Did Church and Turing have a thesis about machines?” by Andrew Hodges. But I’ll be very brief (and not very helpful).

Both papers are about what Fitz calls the Physical Church-Turing Thesis (a function is effectively computable by a physical system iff it is Turing machine computable), and its relative the Machine Church-Turing Thesis (a function is effectively computable by a machine iff it is Turing machine computable). Hodges argues that the founding fathers, as a matter of historical fact, endorsed MCT. I’ve already noted, though, that Copeland in his piece has vigorously and rather convincingly criticized Hodges’s line, and I’ve nothing more to add.

Fitz, however, isn’t so much interested in the historical question as in the stand-alone plausibility of MCT and PCT. He covers a lot of ground very fast in his discussion: some of what he says I found obscure, some points look good ones but need more development, and I’m not sure I’m getting a clear overall picture. But in any case, I can’t myself get very worked about MCT and PCT once we’ve granted that neither is implied by the core Church-Turing Thesis, so I’m probably not paying Fitz quite enough attention. Anyway, I’m cheerfully going to skip on to the next papers.

Tesco’s shows unexpected taste and discrimination

Wow. Tesco Entertainment is selling my Gödel book. Look for piles by the checkouts when publication arrives! I’m booking a world cruise on the expected sales right now.

And on the same page they are advertising another ‘hot product’ (their words), Carol Vorderman’s Maths Made Easy: Ages 3-5, Preschool Shapes and Patterns. Well, I have tried to make my book reasonably accessible: but I’m not quite so sure the markets will overlap.

I think tripos marking is making me lightheaded.

At last, again …

At long last, the final final version of my Gödel book went to the publishers this afternoon. I’ve been taking advantage of a quite unexpected chance to make changes until the last moment — and I think that some that I’ve made in the last month have been quite significant improvements. But now I really do have to stop. And indeed a pile of tripos papers arrived to mark which will prevent me neurotically worrying about stuff that it is too late to change anyway!

It’s an odd feeling, finally letting go. On the whole,as I’ve said before, I’m pretty pleased with the result. To be sure, if I were starting afresh I’d handle a few things a bit differently; and it will be interesting to see if the few sections that still bug me as being really too skimpy technically or philosophically are the ones which reviewers pick up on. But I’m not sure that I could really have sorted them out without making a long book (already at the limits of CUP’s patience) quite a bit longer. So the book will have to take its chances as is!

Phew! A glass or three of Caol Ila seems in order …

The Symposium

A couple of days ago in an Oxfam shop I picked up a second-hand copy of a beautiful parallel text of the Symposium, with a racy and highly readable translation by Tom Griffith and wonderfully evocative wood engravings by Peter Forster. It’s a fun read (though I found the experience tinged with regret at the more or less total loss of my Greek).

But is it still philosophically important? Philosophical interest is not a timeless feature of a text, it seems. No doubt the Symposium is a great source for those looking for clues about the mores of ancient Athens (and that is a fascinating subject: put James Davidson’s Courtesans and Fishcakes on your reading list if you don’t know that terrific exploration). But does the Symposium really tell you anything serious about its ostensible subject, love? Indeed, how do you ‘philosophize’ about that? Read the English poets instead!

Church’s Thesis 6: Concepts, extensions, and proofs

Continuing my blogview of the papers in Church’s Thesis After 70 Years, I’ll skip the contribution by Hartmut Fitz to return to later, and next look at Janet Folina’s ‘Church’s Thesis and the variety of mathematical justifications’ because I’m interested in her main topic, the variety in the idea of proof (I’m just looking one last time at the concluding few sections of my Gödel book, where I talk about this too).

Folina’s paper, though, gets off on the wrong foot. She writes: “Rather than a claim about mathematical objects such as numbers or sets, CT (insofar as it is an assertion) is a claim about a concept. Assessing it requires conceptual analysis.” Which makes it sound as if arguing about CT is like arguing whether the concept of knowledge can be analysed as the concept of justified true belief. But whatever the history of this, nowadays CT is, precisely, a claim about mathematical objects (in the broad, non-Fregean, sense of ‘object’): it’s the claim that a function is effectively computable if and only if it is recursive — or equivalently, if and only if it is Turing computable. And the truth of that extensional claim doesn’t depend on any claim about whether mere conceptual analysis can reveal e.g. that the effectively computable functions are Turing computable.

(Aside: In fact, it is as clear as anything is in this area that, pace Turing, mere conceptual analysis couldn’t reveal such an equivalence, since there is nothing in the notion of an effective computation that demands that the ‘shape’ of our workspace stays fixed during a computation — quite the contrary, we often throw away scratch working, reassemble pages of a long computation etc. — whereas a Turing machine operates on a fixed workspace. It requires a theorem, not conceptual analysis, to tell us that what is computable in a more dynamically changeable workspace is also Turing computable.)

But as I say, Folina’s main remarks are about the notion of ‘proof’ involved in the majority claim that CT is unprovable, and in the minority claim that it is, or might be, provable. She insists that there can be mathematical reasons for a proposition that aren’t proofs, properly so called. Fair enough. But she seems to have in mind the sort of grounds we might have for believing Goldbach’s conjecture. And it isn’t clear to me what she’d say about e.g. the diagonal argument that there are effectively computable functions which aren’t primitive recursive. This isn’t just a quasi-inductive argument, and we’d indeed normally announce it as a proof even though it doesn’t fall under what Folina calls the “Euclidean” concept of mathematical proof, i.e. “a deductively valid argument in some axiomatic (or suitably well defined) system”, given that it involves the intuitive idea of an effectively computable function.

But say what you like here. For even if we allow Folina to reserve (hijack?) the term ‘proof’ for the “Euclidean” cases, the question remains in place whether there can be an argument for CT which is as rationally compelling as the argument that shows that there are effectively computable functions which aren’t p.r., or whether ultimately the grounds are more like the quasi-inductive reasons that support a belief in Goldbach’s conjecture. And that’s the real issue at stake about the status of CT (not whether we call such an argument, if there is one, a proof).

England in May

Near Newton BlossomvilleOften we think about going to live in Italy in a couple of years or so, but it would be a wrench not to see the wooded English countryside in May (we forgot to take the camera when walking last weekend in a quite unregarded area of Bedfordshire — but it was stunning in its quiet way, as even a phone snap hints).

One of the less welcome delights of May, however, is tripos-marking, which starts for me at the end of this week. And before then, I have the tough task of ranking thirty six applications for the Analysis studentship, many of them impressive. So this blog will probably now slow down a bit after the recent flurry of postings.

Church’s Thesis 5: Effective computability, machine computability

The sixth paper in the Olszewski collection is Jack Copeland’s “Turing Thesis”. Readers who know Copeland’s previous writings in this area won’t be surprised by the general line: but truth trumps novelty, and this is all done with great good sense. To take up a theme in my last posting, Copeland insists that ‘effective’ is a term of art, and that

The Entscheidungsproblem for the predicate calculus [i.e. the problem of finding an effective decision procedure] is the problem of finding a humanly executable procedure of a certain sort, and the fact that there is none is consistent with the claim that some machine may nevertheless be able to decide arbitrary formulae of the calculus; all that follows is that such a machine, if it exists, cannot be mimicked by a human computer.

And he goes on to identify Turing’s Thesis as a claim about what can be done ‘effectively’, meaning by finite step-by-step procedure where each step is available to a cognitive agent of limited (human-like) abilities, etc. Which seems dead right to me (right historically, but also right philosophically in drawing a key conceptual distinction correctly, as I’ve said in previous posts).

Copeland goes on to reiterate chapter and verse from Turing’s writings to verify his reading, and he critically mangles Andrew Hodges’s claims (later in this volume and elsewhere) that Turing originally had a wider thesis about mechanism and also that Turing changed his views after the war about minds and mechanisms. I’m not one for historical minutiae, but Copeland seems clearly to get the best of this exchange.

Church’s Thesis 4: Computability by any means

The next paper is “The Church-Turing Thesis. A last vestige of a failed mathematical program” by Carol E. Cleland. Oh dear. This really is eminently skipable. The first five sections are a lightning (but not at all enlightening) tour through the entirely familiar story of the development of analysis up to Weierstrass, Dedekind and Cantor, the emergence of a set theory as a foundational framework, the ‘crisis’ engendered by the discovery of the paradoxes, Hilbert’s formalizing response, the Entscheidungsproblem as a prompt to the development of a theory of effective computation. No one likely to be reading the Olszewski collection needs the story rehearsing again at this naive level.

And when Cleland comes to the Church-Turing Thesis she without comment runs together two importantly different ideas. On p. 133 the claim is [A] one about the ‘effectively computable’ numerical functions — which indeed is the version of the Thesis relevant to the Entscheidungsproblem. But by p. 140 the Thesis is being read as a claim [B] about the functions which are ‘computable (by any means)’. And these are of course distinct claims, requiring distinct arguments. For example, suppose you think that the kind of hypercomputation that exploits Malament-Hogarth spacetimes is in principle possible: then, on that view, there indeed can be computations which are not effective in the standard sense as explicated e.g. by Hartley Rogers, i.e. involving algorithmic procedures which terminate after some finite number of steps. And the questions we can raise about the Hogarth argument are highly relevant to [B] but not to [A].

Cleland’s last section offers some weak remarks about whether computation ‘by any means’ goes beyond Turing computability; but (I’m afraid) nothing here seriously advances discussion of that topic.

Paris 1967, Paris 2007

Well, time to turn to serious matters after such the logical diversions … No doubt you’ve all supported the campaign to absolve Paris Hilton from her prison sentence: after all, in the words of the petition, “She provides hope for young people all over the U.S. and the world. She provides beauty and excitement to (most of) our otherwise mundane lives.” I couldn’t have put it better.

But Guy Debord did, forty years ago (albeit in a French style which isn’t quite mine!):

Behind the glitter of spectacular distractions, a tendency toward making everything banal dominates modern society the world over, even where the more advanced forms of commodity consumption have seemingly multiplied the variety of roles and objects to choose from. … The celebrity, the spectacular representation of a living human being, embodies this banality by embodying the image of a possible role. As specialists of apparent life, stars serve as superficial objects that people can identify with in order to compensate for the fragmented working lives that they actually live. Celebrities exist to act out in an unfettered way various styles of living … They embody the inaccessible result of social labour by dramatizing its by-products of power and leisure (magically projecting them). The celebrity who stars in the spectacle is the opposite of the individual, the enemy of the individual in herself as well as in others. Passing into the spectacle as a model for identification, the celebrity renounces all autonomous qualities …

And there is much more in the same vein, in his La société du spectacle, which I’ve been looking at again (so long after my mispent youth in various leftist groups interminably debating such ideas). Paris 1967 anticipates Paris 2007.

Church’s Thesis 3: Constructivism, informal proofs

The third, short, paper in the Olszewski collection is by Douglas S. Bridges — the author, with Fred Richman, of the terrific short book Varieties of Constructive Analysis. The book tells us a bit about what happens if you in effect add an axiom motivated by Church’s Thesis to Bishop-style constructive analysis. This little paper says more on the same lines, but I don’t know enough about this stuff to know how novel/interesting this is.

The fourth paper is “On the Provability, Veracity, and AI-Relevance of the Church-Turing Thesis” by Selmer Bringsjord and Konstantine Arkoudas. At least these authors get it right about what the core Thesis is: a numerical function is effectively computable if and only if it is Turing-computable. But that’s about as good as it gets. The first main section is a bash against Mendelson’s argument against “the standard conception of the thesis as mathematically unprovable”. Now, although I am sympathetic to Mendelson’s conclusion, I’d want to argue for it in a rather different way (and do so in the Gödel book). But Bringsjord and Arkoudas’s objections just seem badly point-missing about the possibility of a Mendelsonian line. Their argument (p. 69) depends on a bald disjunction between proofs in formal systems and what they call “empirical evidence” for CTT. But of course, tertium datur. Take, for example, the familiar theorem that there are effectively computable functions which aren’t primitive recursive. I’m not being tendentious in calling that a theorem — that’s how the textbooks label the result. And the textbooks, of course, give a proof using a diagonalization argument. And it is a perfectly good proof even though it involves the informal notion of an effectively computable function (the argument isn’t a fully formalizable proof, in the sense that we can’t get rid of the informal notions it deploys, but it doesn’t just give “empirical” support either). Now, the Mendelsonian line is — I take it — precisely to resist that dichotomy formal/formalizable proof vs mere quasi-empirical support and to remind us that there are perfectly good informal proofs involving informal concepts (and Mendelson invites us to be sceptical about whether the informal/formal division is in fact as sharp as we sometimes pretend). And the key question is whether it is possible to give an informal mathematical proof of CTT as compelling as the proof that not all effectively computable functions are primitive recursive. Reiterating the rejected dichotomy is of course no argument against that possibility.

That’s not a great start to the paper (though the mistake is a familiar one). But things then go further downhill. For much of the rest of the paper is devoted to a discussion of Bringsjord’s claim that membership of “the set of all interesting stories” (!!) is effectively decidable but not recursively decidable (Gödel number the stories and we’d have a counterexample to CTT). And what, according to Bringsjord, is the rationale behind the claim that members of that set is effectively decidable? “The rationale is simply the brute fact that a normal, well-adjusted human computist can effectively decide [membership]. Try it yourself!” Well, you might be able to decide in many cases (always? just how determinate is the idea of an interesting story?): but who says that it is by means of implementing a step-by-step algorithm? Effective decidability is a term of art! It doesn’t just mean there is some method or other for deciding (as in: ask Wikipedia or use a cleverly tuned neural net). It means that there is an algorithmic procedure of a certain sort; and in trying to judge whether a story is interesting it most certainly isn’t available to inspection whether I’m implementing a suitable algorithm. This whole discussion just seems badly misguided.

Scroll to Top