FOM: The Church Thesis

Vladimir Sazonov V.Sazonov at
Wed Jan 31 14:16:46 EST 2001

JoeShipman at wrote:
> In a message dated 1/30/01 9:42:30 AM Eastern Standard Time,
> V.Sazonov at writes:
> <<Finally, let me ask, what is the difference between
> CT and any other situation when mathematicians found
> a formalization of an informal concept (like continuity
> in terms of epsilon-delta or topological space) and
> assert a deep satisfaction concerning the relation
> between intuition and its formalization? What is so
> special here about CT? I think - nothing, expect our
> special interest to computability rather than, say,
> to continuity notion. >>
> For the version of the Church-Turing thesis "CT-psych" which asserts
> that any
> intuitively computable function can be computed by a Turing machine,
> we are
> talking about psychology and Professor Sazonov is essentially correct.
>  For
> the version of the Church-Turing thesis "CT-phys" which refers not to
> the
> intuitive notion of computation but to effective procedures, we are
> talking
> about physics and there is a philosophical significance to CT beyond
> the
> assertion of satisfaction that an intuitive concept has been
> formalized.

I do not see any difference and any reason to distinguish
"psyh" from "phys". Intuition means also a "feeling the
reality", in particular, physics. There may be various
intuitions, e.g. of the ordinary digital (physical)
computability or of quantum computability. The goal of
mathematics is to formalize (if possible at all) whatever
intuition we have and to investigate corresponding formalisms
by deductions and translating one into another, etc.
By the way, I would add that "deep satisfaction" of
correspondence between any formalism with an intuition
does not mean "complete satisfaction". There always may be
some unnatural counterexamples such as nowhere differentiable
continuous functions, non-measurable sets, etc. They usually
do not diminish "deep satisfaction" which we have from a good
formalism. Moreover, after formalization, the initial intuition    
can be changed, usually unconsciously.    

Vladimir Sazonov                         
Department of Computer Science           
University of Liverpool                  
Liverpool L69 7ZF, U.K.    

More information about the FOM mailing list