Tuesday, May 29, 2007

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.

1 comment:

Marcin Miłkowski said...

I found Fitz paper very interesting, though he seems to make the classical mistake of making computation basically an interpretation dependent phenomenon. But his views cover a lot of problems discussed usually under the heading 'realization of computation' or 'implementation of computation'. This has to do with CT, of course, but this is an ontological point, not a logical one. And Fitz doesn't seem to appreciate that.