[FOM] Counterfactuals in relative computability theory

[Timothy Y. Chow]

Matthias Jenny wrote:

> 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.

What you refer to as the "philosophical orthodoxy" about abstract objects 
perhaps makes sense for abstract objects that are, or at least are widely 
agreed to be, *mathematically precise*.  For example, integers, strings, 
rules of inference, finite simple groups, Turing machines, and 
error-correcting codes are all mathematically precise.

This "philosophical orthodoxy" is on far shakier ground when it comes to 
abstract objects that fail to be mathematically precise.  For example, 
"large cardinal axiom" and "diagonalization argument" and "simplest proof 
of a theorem" might superficially seem to be mathematically precise 
abstract objects, but they all contain a certain amount of imprecision. 
We know this because when mathematicians are asked to *prove* assertions 
about these objects, they all sense that different people might have 
slightly different ideas about what these phrases mean, and that one must 
choose a particular precise definition before anything can be rigorously 
proved.

The Church-Turing thesis, by its very nature, asserts an equivalence 
between a mathematically precise abstract object (e.g., recursive function 
or Turing machine) and an abstract object that is not mathematically 
precise (algorithm).  In particular, it is not the kind of assertion that 
is susceptible to mathematical proof or disproof.  (At least, this is the 
conventional reading of the thesis.  There is a minority view that the 
Church-Turing thesis might be something that could be proved.  But even 
this minority view acknowledges that the first step would consist of 
further clarifying the "algorithm" side of the equation to the point where 
it is mathematically precise.)

It would not be so controversial to claim that a true assertion of 
equality between two mathematically precise abstract objects is true in 
all possible worlds.  It's far less clear that an assertion of equality 
between a mathematically precise abstract object and a mathematically 
imprecise abstract object is similarly true in all possible worlds.

Indeed, it's not even clear that a mathematically imprecise abstract 
object is a "thing" in the same sense that a mathematically precise 
abstract object is.  If you ask people to imagine how the Church-Turing 
thesis could be false, you'll typically elicit hypothetical scenarios in 
which some algorithm is presented to the mathematical community and the 
community agrees that it meets their tacit criteria for being an 
algorithm, yet the algorithm computes a non-recursive function.  A natural 
way to phrase this situation in terms of possible worlds is to postulate a 
possible world in which there are two distinct mathematically precise 
abstract objects, one of which the community calls an "algorithm" and the 
other of which the community calls a "recursive function."  According to 
this analysis, there is no single abstract object, existing across all 
possible worlds, that is an "algorithm."  In this sense, an "algorithm" is 
not the same sort of thing as a "recursive function."

Tim