[FOM] Counterfactuals in relative computability theory

[Matthias Jenny]

My name is Matthias Jenny and I'm a graduate student in philosophy and
mathematical logic at MIT. John Burgess recommended to me that I reach out
to Martin Davis about a paper of mine about the use of counterfactual
conditionals in relative computability theory. Martin Davis in turn told me
that a discussion of it would be welcome on FOM. Below I'm giving a quick
summary of the main points of the paper. I would be very curious to hear
reactions from people on this list. Thank you.

---

Counterfactuals are conditionals of the form 'If p were the case, then q
would be the case' ('p>q' for short). According to Robert Stalnaker's
(1968) and David Lewis' (1973) semantics for counterfactuals, 'p>q' is true
iff q is true at all possible worlds where p is true that meet certain
further constraints (the details don't matter for present purposes). A
possible world is a complete and consistent specification of a way the
world might have been. Ever since Saul Kripke's (1980) work, it's commonly
accepted that certain sentences are true at every possible world even
though they aren't logical truths. An example is 'Hesperus=Phosphorus,'
which comes out necessary because identity is necessary in quantified modal
logic. Putting these two ideas together, we have what's called the vacuity
thesis: a counterfactual with an impossible antecedent is vacuously true,
and there are vacuously true counterfactuals whose antecedents are
logically consistent. A counterfactual with an impossible antecedent is
also called a counterpossible.

In my paper "Counterpossibles in Science: The Case of Relative
Computability," which is forthcoming in the journal Nous and available as a
preprint here: http://philpapers.org/rec/JENCIS-2, I argue that the role
counterfactuals play in relative computability undermines the vacuity
thesis. I will give a brief summary of my argument.

In his 1958 book, Martin Davis says the following:

"We may ask, of a given problem P,
"If we could solve P, what else could we solve?
"And, we may ask,
"The solutions to which problems would also furnish solutions to P?"
(Davis 1958, 179)

Similarly, in his 1967 book, Hartley Rogers says:

"Intuitively, A is reducible to B if, given any method for calculating [the
characteristic function of B], we could then obtain a method for
calculating [the characteristic function of A.]" (Rogers, Jr. 1967, 127)

And Herbert Enderton, in his 2011 book, says:

"On the one hand, we might be able to show that if, hypothetically
speaking, we could somehow decide membership in B, then we could decide
membership in A. This would lead us to the opinion that A is no more
undecidable than B is." (Enderton 2011, 121)

In section 2 of my paper, I argue that the Church-Turing thesis is
necessary. This means that according to the vacuity thesis,

(1) If the first-order logic were algorithmically decidable, then the
halting problem would also be algorithmically decidable

and

(2) If the first-order logic were algorithmically decidable, then
arithmetical truth would also be algorithmically decidable

are both true. However, I argue that the second sentence is in fact false,
since the decision problem for first-order logic is of Turing degree 0,
whereas the one for arithmetical truth is of degree 0^\omega.

In section 4 of my paper, I go through a number of strategies of resisting
this claim. Perhaps the most promising strategy is what I call the primacy
of oracles. This strategy endorses the following claim:

(3) When relative computability theorists assert (1), what they’re really
doing is assert that there is an algorithm that would allow us to decide
which natural numbers are members of the set coding the halting problem if
we were given complete information about which natural numbers are members
of the set coding all truths of first-order logic.

I discuss this idea on pp. 20-23 of the above preprint. (3) appeals to the
notion of a relative algorithm. Of course, trained computability theorists
have a good grasp of this notion. But it's implausible that this notion is
a pretheoretical one, understood by people with no training in
computability theory. What is a pretheoretical notion, however, is that of
an algorithm. Using it, and using counterfactuals, we can define the notion
of a relative algorithm, similar to the quote from Rogers above.

Let me clarify what I'm not claiming. I'm not claiming that counterfactuals
such as (1) and (2) assume (in contradiction to the mathematical facts)
that there's a Turing machine that can decide first-order logic. Thus, the
antecedent of (1) and (2) isn't mathematically impossible. Rather, what (1)
and (2) rely on is the counterfactual assumption that the Church-Turing
thesis is false. Because, as I argue, the Church-Turing thesis is
necessarily true, (1) and (2) are counterpossibles. But because (2) is
false, this means that the vacuity thesis, and with it the Stalnaker-Lewis
semantics for counterfactuals, is incorrect.

In section 5 and the appendix of the paper, I also describe a semantics for
counterfactuals in relative computability theory that gets the right
results. The semantics is similar to John Burgess' (1981) semantics, but it
uses ideals on Turing degrees as its indices, or "worlds."

---

Matthias Jenny
http://mjenny.mit.edu/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160811/2529bc60/attachment.html>