[FOM] Counterfactuals in relative computability theory

[Matthias Jenny]

On Sat, Aug 13, 2016 at 12:02 AM Timothy Y. Chow <tchow at alum.mit.edu> wrote:

>
> First of all, your claim that the Church-Turing thesis is true in all
> possible worlds is bound to be controversial.  I realize that you didn't
> give the argument here, referring instead to your paper, but it's going to
> be a point of contention for sure.
>

There are a number of arguments for the claim that the Church-Turing thesis
(CTT) is true in all possible worlds. Before I discuss them though, let me
mention that I have an understanding of possibility in mind that is the
orthodox one in philosophy: the one discussed by Saul Kripke in *Naming and
Necessity*. One upshot of my overall argument, if it is sound, may be that
there is a notion of possibility that's less strict than the orthodox
philosophical one and that the vacuity thesis is correct if understood in
terms of that notion of possibility. In any case, here are two reasons for
thinking that the CTT is true in all possible worlds.

1. To say that A isn't algorithmically decidable is to say that there
doesn't exist an algorithm that would allow us to decide A. As Knuth (1966
-- see hhttp://philpapers.org/archive/JENCIS-2.pdf
<http://philpapers.org/go.pl?id=JENCIS-2> for bibliographic reference)
argues, algorithms are abstract objects, so they roughly stand to programs
the way numbers stand to numerals. According to philosophical orthodoxy,
abstract objects are necessary existents: either they exist necessarily or
they don't exist at all. This makes sense: when we say that there doesn't
exist an algorithm that would allow us to decide A, we don't mean that we
haven't found a program to decide it, but rather that there couldn't be a
program to decide it. Thus, if A isn't algorithmically decidable, then
there couldn't have existed an algorithm to decide it, and so it's
impossible for A to be algorithmically decidable. A similar argument shows
that if A *is* algorithmically decidable, then it couldn't have failed to
be algorithmically decidable. So whether A is algorithmically decidable
remains constant accross all possible worlds.

2. Where <> is a possibility operator, the claim that A is algorithmically
decidable can be put as follows: <>(A is algorithmically decided). If the
domain of quantification for <> is the set of *all* possible worlds, then
it follows from the axioms of the modal logic S5, which philosophical
orthodoxy accepts as the correct modal logic, that if <>(A is
algorithmically decided), then ~<>~<>(A is algorithmically decided), and if
~<>(A is algorithmically decided), then ~<><>(A is algorithmically
decided). So again, whether A is algorithmically decidable remains constant
accross all possible worlds.

What reason do we have for thinking that the domain of quantification for
<> is the set of all possible worlds? If it isn't, then the domain is some
more restricted set of possible worlds. One proper subset of the set of all
possible worlds is the set of worlds that are consistent with our laws of
physics. Philosopher often call something that's true in all those
worlds *physically
necessary*. Let <p> be the corresponding possibility operator. So perhaps
to say that A is algorithmically decidable is to say that <p>(A is
decided). But I don't think that that's what Church and Turing had in mind.
They didn't appeal to considerations about the laws of physics to argue
that validity in first-order logic isn't algorithmically decidable. So
their result needs to be understood as stating something stronger than just
~<p>(validity in first-order logic is decided). The next stronger necessity
after physical necessity is commonly thought to be absolute necessity. Of
course, there may be a degree of necessity strictly in between the two. We
can certainly define an operator whose domain of quantification is properly
included in the set of all possible world and which properly includes all
physically possible worlds. But aside from the fact that this would allow
us to hold on to the vacuity thesis, I don't see a reason for thinking that
that's the degree of necessity that Church and Turing had in mind,
especially in light of the argument in 1.


>
> Secondly, there is something strange about interpreting (2) as a
> counterfactual conditional while simultaneously maintaining that the
> Church-Turing thesis is necessary.  My first instinct when trying to parse
> the sentence in terms of possible worlds is to imagine a possible world in
> which first-order logic is algorithmically decidable, and think about
> whether arithmetical truth is also algorithmically decidable in such a
> world.  I can kind of vaguely see how I could interpret the sentence this
> way and even arrive at a judgment as to whether it's true or false, *but
> only if there is at least one such possible world to think about*.
> However, according to you, there is no such possible world, because
> mathematical facts are true in all possible worlds, and the Church-Turing
> thesis is true in all possible worlds.  If you stipulate that, then I'm
> not even sure what (2) *means*, let alone whether it's true or false.  It
> looks to me that you're secretly relying on our intuition that it is
> *possible* for first-order logical to be algorithmically decidable in
> order to get us to agree that (2) is false, and then doing a
> bait-and-switch by arguing that it's not possible after all.
>

Fair enough. But note that as I discuss in section 6 of the preprint, the
semantics I describe makes use of world-like indices. Philosophers
sometimes call such worlds *impossible* worlds (see
http://plato.stanford.edu/entries/impossible-worlds/). So perhaps what
you're thinking about isn't a *possible* world in which first-order logic
is algorithmically decidable, but an impossible one. This of course raises
the question whether we should really call those impossible worlds
impossible. We can certainly define an operator <i> whose domain is
*every *world,
possible or "impossible." But again, I'm happy if an upshot of my overall
discussion is that the vacuity thesis needs to be understood in terms of
every world, including the "impossible" ones.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160813/a63bcb2b/attachment.html>