[FOM] Counterfactuals in relative computability theory

Timothy Y. Chow tchow at alum.mit.edu
Thu Sep 1 16:42:19 EDT 2016

Matthias Jenny wrote:
> I agree that if that's how we understand the Church-Turing thesis, then 
> it's not true in all possible worlds. But as I'm sure you're not 
> surprised to learn, I'm not convinced that this interpretation is 
> accurate. After all, when textbooks give defenses of the Church-Turing 
> thesis, they hardly ever point to sociological facts.

I'm not convinced it's accurate either, but I certainly don't think 
there's a consensus on this point.  In particular, I'm surprised to see 
that you think that textbook discussions don't point to sociological 
facts, since in my experience, they almost always mention that 
sociological fact that there was rapid acceptance of the Church-Turing 
thesis after three different definitions were shown to coincide (indeed, 
you mentioned this sociological fact yourself).

Occasionally one encounters people who try to argue that 
"hypercomputation" presents a potential challenge to the Church-Turing 
thesis.  As I've argued on FOM before, I don't find their arguments 
convincing. but the fact that these arguments have gained some traction 
demonstrates that some people's definition of "algorithmically decidable" 
does not necessarily exclude things that are non-Turing-computable.


More information about the FOM mailing list