[FOM] Counterfactuals in relative computability theory

Fri Aug 12 13:23:56 EDT 2016

	  My ideas about counterfactuals run along the lines of “If wishes were horses, then beggars would ride”  or “Sh-t in one hand, hope in the other; see which fills up first." <— Obviously inappropriate for FOM and should be rejected without Martin batting an eye, but I hope he may snicker a bit.  On a less unserious note, “If the impossible were possible, nothing would be impossible.” <— For this, I’d like to see a more perceptive analysis than what’s on the surface (probably impossible for possible-world analysis of any depth). 

> On Aug 11, 2016, at 6:59 PM, John Burgess <jburgess at princeton.edu> wrote:
> 
> OK, I finally see what I was not understanding about your proposal. I took you to be considering conditionals whose antecedents were denials of mathematical truths, but you only mean them to be denials of the Church-Turing thesis or things implying that denial. I still don't think this is what the quotations mean, but I do see that merely assuming validity effectively decidable even though not decidable by a recursive function or a tape machine will not give in any direct way the effective decidability of arithmetical truth.
> 
> On 11Aug  16, at 3:30 PM, Matthias Jenny wrote:
> 
>> 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 <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/ <http://mjenny.mit.edu/>
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu <mailto:FOM at cs.nyu.edu>
>> http://www.cs.nyu.edu/mailman/listinfo/fom <http://www.cs.nyu.edu/mailman/listinfo/fom>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160812/0f05d466/attachment.html>