[FOM] Counterfactuals in relative computability theory

[Matthias Jenny]

On Sun, Aug 21, 2016 at 8:13 PM Timothy Y. Chow <tchow at alum.mit.edu> wrote:

> Thanks for your clarifying comments.
>
> I'm going to take another stab at sketching your viewpoint, by means of a
> fictional story.  You can tell me if I'm on the right track or not.
>
> The Heine-Borel theorem states that a subset of Euclidean space is compact
> if and only if it is closed and bounded.  "Compact" means that every open
> cover has a finite subcover.
>
> On my last trip to Mars I discovered that the Martians are very similar to
> us, except that when they talk about "compact" sets of Euclidean space,
> they take themselves to be using the word "compact" in an informal sense.
> They offer no precise mathematical definition, but they seem to know a
> compact set when they see one.
>
> I also learned that, historically, there was a time when they thought that
> maybe the right way to formally define the predicate "is compact" was "is
> a finite union of closed intervals of finite length."  Then one day
> some clever Martian came up with the set {0} U {1/n : n >= 1} and they all
> agreed that it was compact.
>
> Nowadays, the accepted wisdom among Martians is that a subset of Euclidean
> space is compact if and only if it is closed and bounded.  By a remarkable
> coincidence, they call this the "Heine-Borel thesis."  They don't call
> this a theorem because it identifies a precise mathematical concept
> "closed and bounded" with an informal concept "compact."
>
> My resident Earthling expert on Martian culture, Jenny Matthews, was of
> the opinion that the Martian "Heine-Borel thesis" was really the same as
> the Earthling "Heine-Borel Theorem" and was therefore true in all possible
> worlds.  The Martians were missing a piece of knowledge, namely that their
> "compact sets" were *precisely* the same as "sets with the property that
> every open cover has a finite subcover."  In the absence of this piece of
> knowledge, they felt that the word "compact" was informal and not precise,
> but unbeknownest to them, the true content of their Heine-Borel thesis was
> an equation between two precise concepts, and therefore was true in all
> possible worlds.
>
> Returning to Earth and reflecting on the Church-Turing thesis, I wondered
> if perhaps the predicate "is an algorithm" had the same status as the
> Martian predicate "is compact," in the sense that it referred to some
> precisely delimited property, even though the consensus among Earthlings
> was that "is an algorithm" is informal and imprecise.  Perhaps the
> Church-Turing thesis is just an epistemologically challenged version of an
> unknown Church-Turing theorem that is true in all possible worlds, and is
> therefore also true in all possible worlds?
>
> Is this an accurate reconstruction of your view?
>

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160822/25e6ccea/attachment.html>