Church’s Thesis 11: Its status, once more

As you can imagine, it is going to be pretty difficult, by this stage in the game, to say something both novel and illuminating about ‘The status of Church’s Thesis’. And certainly, Roman Murawski and Jan Wolenski don’t really succeed in their paper of that title.

They don’t help their cause by seeming to vacillate from the start about how to understand Church’s Thesis itself. Their official story is clear enough: CT is the claim that a function is effectively computable if and only if it is (partial) recursive. Fine: by my lights, that’s the right thing to say. But note, this makes CT a doctrine in the realm of reference. But then Murawski and Wolenski immediately offer, without any comment on the mismatch, quotations from Kalmar and Kleene which talk of CT as stating ‘the identity of two notions’ or as supplying ‘previously intuitive terms … with a certain precise meaning’ — talk which is only really appropriate if CT is taken as a doctrine in the realm of sense. Of course, our belief that the extensions of ‘effectively computable function’ and ‘recursive function’ are the same may well be grounded in beliefs about the relation between the senses of those expressions: but we surely ought to be clear here when we are talking about sense, and when we are talking about reference.

Anyway, Murawski and Wolenski proceed to distinguish four lines that have been taken about the status of CT, of increasing plausibility according to them: (1) it is an empirical hypothesis, (2) “is an axiom or theorem”, (3) it is a definition, (4) it is an explication.

But they seem just confused in supposing that (1) people have supposed that CT — as they have officially defined it — is an empirical hypothesis. Rather, it is claims like “every humanly computable function is recursive”, or “every function computable by a physically realizable machine is recursive”, that have been thought to be empirical. And as I’ve stressed before in this series of postings, CT is to be distinguished from those quite different claims. So put (1) aside.

Now, as Mendelson famously stressed, the easy half of CT looks to have a perfectly good informal proof (it is an informal theorem, if you like). Running the argument for total functions: the initial functions are plainly effectively computable; definitions by composition and recursion preserve effective computability; and definition by regular minimization preserves effective computability too. But all total recursive functions are definable from initial functions by composition, recursion and/or regular minimization. So all total recursive functions are effectively computable. Mutatis mutandis for partial recursive/partial computable functions. QED. So if we are to reject (2) we need a good reason to suppose that it is impossible to run a comparable argument for the difficult half of CT. But Murawski and Wolenski change the subject twice. First, they talk about what would be needed for a formal proof of CT and the problem of showing that “the axioms of the adopted axioms for computability do in fact reflect exactly the properties of computability (intuitively understood)” which looks too much like the problem of establishing CT. But whatever the force of those remarks about formal provability, they don’t in themselves sabotage the possibility of an argument for the hard half of CT which, while informal, is as cogent as the familiar argument for the easy half. Then secondly, Murawski and Wolenski go off at a tangent talking about the role of CT in proofs: but that’s irrelevant to (2).

We can skip over (3) as such remarks about CT as a definition that we find in the Founding Fathers actually don’t seem to distinguish the thought from (4). The real options do indeed seem to be (2) — understood as a claim about there being an informal proof for CT — versus (4). Murawski and Wolenski worry a bit about the kind of explication CT could provide, given that they say “it replaces a modal property of functions by one that is non-modal”. But while there may be worries about the notion of explication here, that isn’t one of them. For “f is effectively computable” is in the current context equivalent to “there is an algorithm which computes f”. So there isn’t anything excitingly modal going on.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top