Tuesday, May 15, 2007

Church’s Thesis 2: What’s an algorithm?

Andreas Blass and Yuri Gurevich’s paper “Algorithms: A Quest for Absolute Definitions” really covers too much too fast to be very satisfactory. The first part is a quick review of the separate histories of Church’s Thesis and Turing’s Thesis, followed by a quick overview of the path from Turing’s original analysis of what we might call a classical algorithmic procedure to its generalization in the work of Kolmogorov and Uspenskii, and Schönhage. But they also say

In fact the notion of algorithm is richer these days than it was in Turing’s days. And there are algorithms ... not covered directly by Turing’s analysis, for example, algorithms that interact with their environments, algorithms whose inputs are abstract structures, and geometric or, more generally, non-discrete algorithms.

And they go on to describe very briefly -- or at least, too briefly for this reader -- some of work on more abstract general notions of computation.

But, by my lights, once we go beyond Kolmogorov and Uspenskii we lose touch with discussions that are directly relevant to the Church-Turing Thesis, construed as a claim about effectively computable functions (where the notion of effective computability is elucidated in the traditional way, in terms of what can be done by a sequential, step-by-deterministic-step procedure, where each small step is available to a computing agent of limited cognitive abilities, etc.). And indeed, Blass and Gurevich themselves don't challenge the Thesis: their concern is more with extensions of the core concept of an algorithm -- or at least, that’s how I prefer to describe what they are up to.

No comments: