[FOM] Counterfactuals in relative computability theory

Matthias Jenny mjenny at mit.edu
Wed Aug 24 16:00:35 EDT 2016


On Tue, Aug 23, 2016 at 5:56 PM <W.Taylor at math.canterbury.ac.nz> wrote:

> Still, it seems that any definition given (necessarily) in words, i.e. that
> cannot be pared down to a strictly mathematical one, must retain *some*
> element of some sort of imprecision, if only because natural language does
> so.
>


I agree that if we cannot provide a strictly mathematical definition of a
concept then we have no antecedent guarantee that the thing the resulting
concept is a fully precise one. But I think it may nevertheless happen that
the resulting concept is fully precise. I believe that that's what happened
in the case of 'algorithm' (and in the case of 'algorithmically
computable').


> However; this and other posts have brought something to mind that might
> be worth considering.  We have all been wondering whether, in some sense,
> "algorithm-ness" is somehow equivalent to "effectiveness".  But there is
> already a considerable literature on computability with respect to access
> to various sets of naturals, i.e. to "oracles".   This idea surely easily
> extends to algorithms with oracle-access.  This might help define the
> extent
> to which some sort of borderline might exist.  And maybe even help to show
> that the CT thesis is perhaps not so much about computability per se,
> but more about the nature of "oracles"?
>

I'm not sure I'm following this. The Church-Turing thesis is about what can
be done with algorithms. It's true that there's a notion of relative
algorithm, but that's a different notion (unless we only supply only
oracles for computable sets, in which case the whole exercise would be a
bit pointless).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160824/d8c31214/attachment.html>


More information about the FOM mailing list