realism vs. Church-Turing Thesis

From: Wei Dai <>
Date: Tue, 16 Jul 2002 12:06:05 -0700

On Fri, Jul 12, 2002 at 06:47:46PM +0200, Bruno Marchal wrote:
> Those I have encapsulated in the label "comp". Precisely it consists in
> 1)accepting a minimal amount of arithmetical realism, i.e. the truth of
> elementary statements of arithmetic does not depend of me or us ...
> 2) the Church Thesis (also called the Church Turing Thesis, or the
> Post Law, etc.)
> i.e. all universal machine are equivalent with respect to their simulation
> abilities (making abstraction of the duration of those simulation).
> 3) [skipped]

Couple of questions that arise from reading Hartley Rogers's book. Why
stop at arithmetical realism? Why not analytical realism (truth of
statements of analysis does not depend on us) or set theoretic realism
(truth of statements of set theory does not depend on us), both of which
are stronger than arithmetical realism?

Isn't (even) arithmetical realism incompatible with the Church-Turing
Thesis, because no Turing machine can enumerate all true statements of
elementary number theory? (BTW, according to, there is quite a bit of
confusion about what people mean by the Church-Turing Thesis. Could you
take a look at that article and tell me which version of the Thesis you
have in mind? For now I'll assume that you mean what the article refers to
as Thesis M.) So why do you restict your Universal Dovetailer to be a
Turing machine? Why not one of the more powerful machines surveyed in
Received on Tue Jul 16 2002 - 12:06:57 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST