*I asked this some days ago over at math.se, and while the question got 10 upvotes, I didn't get too many answers. Although it is a "soft question", maybe the general issue is interesting enough to raise again here in the hope of more answers.*

The Church/Turing Thesis that we all know and love asserts that every algorithmically computable function (in an informally characterized sense) is in fact recursive/Turing computable/lambda computable. A certain intuitive concept, the Thesis claims, in fact picks out the same functions as certain (provably equivalent) sharply defined concepts.

Evidence? Two sorts: (1) "quasi-empirical", i.e. no unarguable clear exceptions have been found, (2) conceptual, as in for example Turing's own efforts to show that when we reflect on what we mean by algorithmic computation we get down to the sort of operations that a Turing machine can emulate.

OK, now compare. The "Eilenberg/Mac Lane Thesis" in one version (but does anyone call it that??) is that if an isomorphism between widgets and wombats is intuitively "natural" (i.e. doesn't depend on arbitrary choices of co-ordinates, or the like) then it can be regimented as an natural isomorphism between suitable functors in the official category-theoretic sense. A certain intuitive concept, the Thesis claims, in fact picks out the same isomorphisms as a certain sharply defined concept.

Evidence? We'd expect two sorts. (1*) "quasi-empirical", i.e. no clear exceptions. (2*) conceptual ...

Two main questions:

(A) But *are* there no exceptions? Or (to take the perhaps more likely direction of failure) are there well known cases where we can say "Hey, this is the sort of isomorphism whose intuitive naturalness was surely of the kind that Eilenberg/Mac Lane were trying to chraracterize, back in the day: but actually, you can't shoehorn this case into the framework of their theory of natural isomorphisms."

(B) Assuming the Thesis isn't defeated by counter-example (or is true for some nice class of cases), what are the best efforts at trying to show that, conceptually, it "ought" to be true (when it is)?

And then I suppose that there is a supplementary question arising of category theoretic etiquette:

(C) Assuming again the Thesis isn't obviously defeated by counter-example, is it secure enough for it now to be acceptable to slide without further argument from showing that there is an isomorphism between widgets and wombats constructed in an intuitively "natural", unarbitrary, way to announcing that there is therefore a natural isomorphism here?

isomorphisms. $\endgroup$ – Eric Wofsey Jul 14 '15 at 7:49