[FOM] Counterfactuals in relative computability theory

[Timothy Y. Chow]

Matthias Jenny wrote:

> This fictional story is very helpful. The only thing I would disagree 
> with is that 'is an algorithm' is imprecise. I think it's informal, but 
> not imprecise, unless 'imprecise' means the same thing as 'informal' 
> here. But if by 'imprecise' we mean something like being subject to 
> sorites series ('is red' is imprecise in that sense), then I don't think 
> 'is an algorithm' is imprecise. That's because I don't think there are 
> any borderline cases of 'is an algorithm.' I'd be curious to hear 
> whether you think that there are.

I'm not sure I have a fully settled opinion about the exact nature of the 
Church-Turing thesis, but I do think your interpretation of it is 
nonstandard.

I think that one common view of the word "algorithm" (or the word 
"algorithmic" or the predicate "is an algorithm"---frankly, it seems 
pedantic to me to insist on one particular form) is that the reason it is 
informal is that the scientific community came to adopt the term via an 
organic, pre-theoretical process.  No official agreement about what the 
term meant was ever laid out explicitly.  So you might ask three different 
people what it means and get four different answers.  In this sense the 
word is vague.  I don't think that this is quite the same kind of 
vagueness you're alluding to when you mention sorites and borderline 
cases.  That makes it sound like you at least have a precisely defined 
"ground set" and the only thing undetermined is precisely which subset of 
the ground set coincides extensionally with the allegedly vague predicate. 
I don't know that everyone would agree that "is an algorithm" is as 
precise as that.  For comparison, we might consider the term 
"philosophical argument."  What constitutes a philosophical argument?  I 
don't think one can come up with a clearly defined set of precisely 
defined objects with the property that every philosophical argument can be 
identified with a specific member of the set, with the only thing left to 
debate being which members of the set are philosophical arguments and 
which are not.

Now, I do agree that once the Church-Turing thesis is brought into the 
picture, then we have some reason to question the claim that "algorithm" 
is as vague as "philosophical argument."  After all, the popularity of the 
Church-Turing thesis indicates that many people seem to be willing to 
*equate* the informal term "algorithm" with a formal concept.  If I were 
to exclaim, "Wait a minute!  You can't have an equation where one side is 
a precise concept and the other side is an irremediably vague one; that's 
a category error!" then I wouldn't expect to garner much sympathy.  Maybe 
the community's willingness to embrace the Church-Turing thesis is an 
indication that the allegedly vague concept of "algorithm" *was actually 
precise all along and we just didn't realize it until now*.  That would 
seem to be your contention.

On the other hand, there are other ways of looking at the situation.  We 
could, for example, regard the Church-Turing thesis as a *sociological 
prediction*.  It predicts that anything that the community agrees on in 
the future to be "algorithmic" will turn out to be "Turing-computable." 
That is, the Church-Turing thesis is not some sort of epistemologically 
challenged version of claim about how things are in the Platonic realm of 
formal objects, but is a claim about human behavior.  Under this view, it 
is harder for me to see how it could be true in all possible worlds.

In any case, I still cling to my main claim, which is that your account of 
the nature of the Church-Turing thesis is really the crux of what you're 
arguing, rather than all that stuff about the vacuity thesis and relative 
computability theory.

Tim