[FOM] Counterfactuals in relative computability theory

[Matthias Jenny]

On Sun, Aug 14, 2016 at 8:29 PM Timothy Y. Chow <tchow at alum.mit.edu> wrote:

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

I'm not sure I have a clear grasp of the notion of a mathematically precise
object. Take a sorites series of tiles where the first tile is red, the
last tile is orange, and there is no distinguishable difference between any
two adjacent tiles. It's unclear in this case whether the definite
description 'the number of red tiles in the series' succeeds in picking out
a particular natural number. According to some theories of vagueness, it
does, and according to others, it doesn't. Suppose it does, and suppose the
number it picks out is n. Surely, n is a mathematically precise object.

It's true that I was supposing that 'algorithm' determinately picks out
exactly one property. And I realize that that's potentially controversial,
so I should have made that explicit. Steward Shapiro thinks that at least
in the 1930's, 'algorithm' didn't pick out a determinate property. But I'm
not sure he thinks that it doesn't pick out a determinate property today.


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

I think what's difficult about proving the Church-Turing thesis is that we
can't give a reductive analysis of 'algorithm' in terms of concepts that
are understood to determinately pick out properties and objects. It strikes
me that the lesson to learn from that is that we should accept 'algorithm'
as a primitive concept and attempt to axiomatize it, which is exactly what
the likes of Wilfried Sieg and Yiannis Moschovakis have attempted to do. Of
course, as you point out, this would still leave us without a proof that
the axiomatization is correct. But just because some axioms can't be proven
mathematically doesn't mean that the concept that they axiomatize aren't
precise. Sure enough, some people think that 'set' doesn't pick out a
determinate property. But it doesn't follows that these people are right
simply because of the fact that the axioms of set theory can't be proven
mathematically.


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

It strikes me that, given that 'recursive function' and 'Turing machine'
pick out determinate properties, 'algorithm' would have to do so as well in
order for the Church-Turing thesis to be true *in this world*. So if the
Church-Turing thesis is true in this world, then 'algorithm' picks out a
determinate property, in which case I believe that my argument for the
necessity of the Church-Turing thesis goes through.


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

I don't think that the scenario you describe is a sufficient condition for
something to be a counterexample to the Church-Turing thesis. Surely we'd
need to assume that the community *correctly* call one of the two objects
'algorithmically decidable' and that they *correctly *call the other one a
'recursive function.' I think that what you describe is the process through
which the community would discover a counterexample to the Church-Turing
thesis, not the counterexample itself. (Of course, I realize that what I
just said is much more plausible if we assume that 'algorithm' picks out a
determinate property.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160815/da1ddd0a/attachment.html>