[FOM] Counterfactuals in relative computability theory

[Matthias Jenny]

On Wed, Aug 31, 2016 at 10:57 PM Timothy Y. Chow <tchow at alum.mit.edu> wrote:

>
> 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 agree that, especially prior to 1936, different people would have
provided different definitions of 'algorithmically decidable' or related
concepts. However, I don't think that this establishes that these different
definitions wouldn't have agreed on what the set of algorithmically
decidable sets is. I take the convergence of the models provided by Turing,
Church, Gödel & Herbrand, etc. to indicate that the various definitions
that people would offer of 'algorithmically decidable' would have coincided
exactly. It's in *this* sense that I think the word isn't vague.

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.
>

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160901/4ab7e4c1/attachment-0001.html>