[FOM] Counterfactuals in relative computability theory
Timothy Y. Chow
tchow at alum.mit.edu
Wed Aug 31 22:18:28 EDT 2016
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
More information about the FOM
mailing list