Formalising Church's Thesis
Peter Ladkin
in sci.philosophy.teck, jamie andrews wondered whether there could
ever be a set of principles of computability with respect to which
church's thesis would become provable, rather than a metaphysical
principle, which it seems to be at the moment. he suggested the
analogy with the concept of infinity, which is a central part of
modern mathematics, but which had the status of a metaphysical idea,
and was only formalised coherently less than a hundred years ago.
i'm posting this to sci.math as well because there may be some interest
in this amongst other mathematicians. i've directed followups to
sci.logic and sci.philosophy.tech, which seem to be the proper place
to continue.
In article <20...@princeton.Princeton.EDU>,
rks@notecnirp (Ramesh Sitaraman) writes:
>[...] to formalise Church's
>hypothesis one needs to formalise what an "informal" notion
>of computation. [..] The only kind of validation one
>can hope for (like experimental valiadation in physics), is that
>all that we have thought so far as valid computations can be coded
>as a TM.
i don't agree with the second sentence, although i probably agree with the
first. jamie andrews mentioned an analogy with the concept of infinity.
there are some similarities as well as differences.
since this posting is rather long, i'll summarise what's in it,
in the next few paragraphs.
i went back to look at some of the history of notions of infinity so
that disanalogies with the case of church's thesis would become clear.
i summarise briefly the views of leibniz and kant (and comment on
locke, spinoza, descartes and aristotle as well). basically, they all
thought the notion of completed infinity and/or infinite number to
involve a reductio ad absurdum with important metaphysical principles.
it was left to frege to produce a coherent account (with help from cantor).
church's thesis is in a different state - almost everyone thinks it's
true. this may be why ramesh thinks it can only be `experimentally
validated' - which i think is an incoherent notion in this case.
he is confusing *validation*, which for a universally quantified
statement such as church's thesis may only be done via a general proof,
with *invalidation*, which may be done by exhibiting a single instance
that does not fit the scheme. thus one may only *invalidate* the thesis
experimentally, not validate it.
but is church's thesis true? tarski conjectured that it was not, and
gave a scheme for a computable function that was not general recursive.
pete wells (a student of tarski) constructed a class of functions that fit
the scheme. so there is a counterexample. but as in the case of infinity,
`counterexamples' actually turn into a different kind of creature (see
lakatos: proofs and refutations for an explanation of these kinds of
synthesis). so just as there are completable and non-completable
infinities (i.e. kant, leibniz at al were right after all) so there
are churchian and non-churchian computable functions. one can
reasonably hope, as jamie andrews does, that such results will lead to
yet more insightful characterisations of computable functions.
end of summary. now on to the details.
firstly, i summarise the views of
various oldies but goodies (esp. kant and leibniz) on infinity (because
i got curious about the analogy with the situation with church's thesis),
and then i describe the tarski/wells counterexample in a little more
detail (from memory, because i don't think it's been published).
firstly, as far as the history of infinity, the crucial idea was to
conceive of an infinite progression as a completed whole. this may seem
vague, so let me try to be more precise. there were a number of arguments
around, including some by kant, to the effect that all infinite
progressions were unbounded, and these arguments were used to justify
some fairly strong metaphysical claims. for a brief survey of this,
i recommend jonathan bennett's book `kant's dialectic', chapter 7.
for kant `the infinity of a series consists in the fact that it can never
be completed through successive synthesis'(bennett p118, l6). kant did
not like the idea of an infinitely receding past, since there would at
any instant have to be a completed infinity of past moments, but he was
happy with the idea of a future infinity, since every stage of constructing
a future infinity is finite, and the future infinity is never completed.
part of the compulsion of this argument rests upon comprehending infinite
successions as `non-finite' i.e. that which is not finite, and it is
one of the characteristics of finite successions that they are completed.
this is an equivocation, as we now know, but some great minds
fell for this. spinoza found absurd
the notion of one infinity's being greater than another (bennett, p126,
footnote 17), and if there were an infinite number, say the number of
natural numbers n, then there must be the number m of even numbers, and
since there are more naturals than evens, n must be greater than m,
reductio ad absurdum. of course, the fact that n and m are the *same*
number was a great discovery of cantor and frege. descartes (according
to bennett) was agnostic about whether one infinite number could or
could not be greater than another, but also suggested that something
`would no longer be infinite, were we able to comprehend it' (bennett p126).
thus for him too, infinities are not completable.
leibniz accepted that n=m above, but again believed this was a reductio
ad absurdum, since `the whole is not greater than the part' (bennett p126).
leibniz actually had a fairly sophisticated theory of number according to
which there is indeed no infinite number (bennett gives a brief explanation.
also see rescher, `leibniz: an introduction to his philosophy, X.7.
X footnote 73, p108 quotes the argument about number). as rescher points
out, the whole not being greater than the part came to be a defining
characteristic of infinite numbers, though to leibniz it was an impossibility.
so although all these gentlemen allowed `a multitude of things which surpasses
any finite number' as comprehensible, they also inferred that it does not
follow that there is an infinite number, or a completable infinity.
Locke also subscribed to this (bennett p127), and Aristotle indeed
had an argument that `number taken in abstraction cannot be infinite'
because `that which has number is numerable', and thus capable of
being `gone through', whereas `infinite' can mean `what is incapable
of being gone through'. so there.
And indeed there are many coherent parts to this view in general.
constructivist mathematicians (especially intuitionists) are more careful
about completable/incompletable infinities than classical mathematicians,
for whom the main incompletable infinity is the cumulative hierarchy of
sets (a.k.a. V). for intuitionists, real numbers may be identified with
choice sequences, which are incompletable sequences of choices of natural
numbers. dummett (principles of intuitionism, p55) says `in intuitionist
mathematics, all infinity is potential infinity: there is no completed
infinite'. so maybe kant and leibniz were right, but for the wrong reasons.
ranking aristotle, descartes (the cynical agnostic), spinoza, locke
and kant amongst those who thought there could be no completed infinity,
and/or no infinite number, one can comprehend the magnitude of frege's
achievement (with some help from cantor) in constructing a coherent
account (if one is not an intuitionist) of infinite number.
frege approached the idea through that of cardinality, and eventually
defined cardinal numbers. cantor had done a lot of the technical work
on sets that frege needed to establish his theory. one can imagine why
frege stopped working when he thought russell had shown his work to be
fundamentally flawed. luckily, there was no golden gate bridge close
to hand.
so the disanalogy with church's thesis is that most great philosophers
(hume is notably missing from this picture) had arguments against
completed infinities, but they were all mistaken in one way or another
(if one is not an intuitionist, that is). it required an enormous
intellect, not to mention chutzpah, to buck the trend. you could not
argue against the mistakes a priori, because the arguments looked
good. one needed to *show* how a coherent completed infinity/infinite
number could be defined. in the case of church's thesis, most people
believe it's true and are looking for rigorous arguments to uphold it.
an analogy between the case of infinity and church's thesis would be
to *show* how the thesis is mistaken by exhibiting a computable
function which is not general recursive. which of course you can only
do if church's thesis is false. it may indeed be false. but if the
line of argument is that it is true (and maybe provable), one has a
very different task ahead.
is church's thesis false? tarski wondered whether there could be a
computable, but non-general-recursive function. i'll have a shot at
giving the general idea, but i'll probably botch it. the idea is that
for each n, there is a general recursive function f_n(x) that will
compute one value. but the *class* of functions {f_n(x): n in N} is
not general recursive. so the function g(n) = f_n(n) is arguably
computable (since for every value there is a general recursive
function that computes it), but not general recursive (obviously, one
needs to show that it's not for a specific class of functions - it
doesn't follow immediately). here there is an analogy with infinity.
the cumulative hierarchy of all sets is one of those incompletable
infinities, and the arguments that it cannot be a set are precisely
the arguments (suitably formalised) that leibniz et al used to rubbish
the notion of completable infinity. tarski had the idea that there
may be, by analogy, an incompletable (i.e. not recursive) hierarchy
of completable (recursive) functions, one could use it to compute
values, in the same way that one can count natural numbers for ever,
or, even with completable infinities, ordinals for ever. one is indeed
computing, and the collection of the results you get form the
definition of a function.
pete wells (aka benjamin f. wells), the translator of mal'cev and one
of tarski's students, liked this idea (and so do i). pete's thesis
(the last that alfred signed before he died) produced precisely such a
class of functions. to my knowledge, he hasn't published it yet. he
now teaches at the university of san francisco (not to be confused
with ucsf, the med center).
so one may argue that church's thesis has already been shown to be false.
probably the right thing to argue is that there are two different notions
of computable, and then to enumerate the differences between them, by
analogy with the case of completable infinities (the natural numbers,
rational sequences), and incompletable infinities (the universe of all sets).
one can therefore hope to have a proof for one notion of computable
that it coincides with general recursive, and that another notion
(via wells's result) does not.
peter ladkin
Barry W. Kort
will continue to hear from him from time to time.
I must admit that reading Peter is like drinking from a firehose.
I think I would benefit from smaller doses, more frequently
administered. :-)
--Barry Kort