[FOM] Counterfactuals in relative computability theory

[John Burgess]

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, 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/
> _______________________________________________
> 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/20160811/44367297/attachment-0001.html>