[FOM] Counterfactuals in relative computability theory

[Timothy Y. Chow]

Matthias Jenny wrote:
> 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.

Correct me if I'm wrong, but it looks like you're billing this as an 
argument that certain technical facts in computability theory imply that 
the vacuity thesis is wrong.  But it doesn't look like that at all to me 
since there are other, more debatable, premises in your argument.

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.

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.

Tim