Thursday, May 17, 2007

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.

No comments: