Re: *THE* PUZZLE (was: ascension, Smullyan, ...)

From: Tom Caylor <>
Date: Sat, 17 Jun 2006 21:35:49 -0700

Bruno Marchal wrote:
> Le 15-juin-06, à 13:53, Tom Caylor a écrit :
> > OK. I think I understand what you are saying, on a surface level. Of
> > course a surface level will never be able to expose any contradictions.
> > I'm just riding this wave as long as I can before deciding to get off.
> >
> > It seems that there are very deep concepts here. We are standing on
> > the shoulders of computability giants. I think it would take a Godel
> > or a Church or Turing to find any problem with your whole argument, if
> > there is any. My feeling is that any "problem" is actually just lack
> > of deep enough insight, either on the part of the attempting-refuter of
> > the argument, or on your part, or both.
> >
> > By the way, I am also cognizant that what you are covering here
> > actually is pretty standard stuff and actually has been pored over by
> > the giants of computability. So like I said, I'm riding the wave.
> >
> > On a certain level, it bothers me that Church's Thesis is said to not
> > have any proof. But maybe it is sort of like Newton's gravity. It is
> > just a descriptive statement about what can be observed. And yet... we
> > still don't really understand gravity. Here we are at the level where
> > all there is is falsifiability.
> OK. Note that Church thesis has a unique status in math. I will come
> back on this.
> > And, by the same diagonalization
> > argument, you'd have to be God to falsify this "stuff".
> Ah... but here you are wrong. Church thesis, although not entirely
> mathematical, still less physical, is completely refutable in the sense
> of Popper (and thus "scientific" in the "modern" acceptation of the
> word). To refute Church thesis it is enough to find a function F such
> that you can show:
> 1) F is computable, and
> 2) F is not Turing emulable.
> Some people, like Kalmar, has thought they got such a function, but
> this has been rebuked.

I don't know much about Church Thesis, but I want to learn more. Even
though it seems easy to recite, as in the existence of a Universal
Language, it seems very deep and mysterious. Almost like stating a
Unified Field Thesis. You just state it, and then see where it leads,
at least as far as you are able to follow it.

But on the surface, the very prospect of someone trying to disprove
Church Thesis is funny to me. Perhaps I am missing something. To
think of a counterexample seems like a contradiction. Didn't Turing
describe his Turing machine as equivalent to what a mathematician can
do with a pencil and paper? But the counterexample would have to be
something that someone (probably a mathematician ;) could think up! So
a counterexample would be a function F that

1) a mathematician could think up
2) without using a pencil and paper! Oooo.

Actually, I am aware that people like Penrose actually say that
something is going on in the brain (quantum-mechanically) that could
never happen on a piece of paper. But putting it in the above way
makes it sound funny. And I think actually Penrose might claim that
the function G is just such a function. He doesn't say much in his
Shadows of the Mind about Church Thesis. But, Bruno, your posts on
this seem to be assuming Church Thesis and then seeing what the
conclusion is about G, which is perhaps the opposite of Penrose.

Do you think that there is a possibility that Church Thesis has the
same status as the Continuum Hypothesis in this sense: the Continuum
Hypothesis has been shown to be independent of the axioms of
arithmetic, i.e. both the truth and the falsity of the Continuum
Hypothesis is consistent with the axioms of arithmetic. Could the
Church Thesis be independent of... what?... The problem is: what body
of knowledge is there that is in the pursuit of truth, and is also
intimately affected by the Church Thesis? The mind-body problem, I
guess. Could the Church Thesis be independent of the mind-body


> Eliot Mendelson has argued that CT is provable, and sometimes I share a
> little bit that feeling. I did believe that CT is provable in "second
> order arithmetic" for a time because it did seem to me that CT relies
> above all on the intuition of the finite/infinite distinction. But then
> it could still be subtler than that, and I am not sure at all CT could
> really be proved.
> Note that I talk only on the classical Church thesis, not about its
> intuitonistic variants, which I do believe are false for the first
> person associated to the machine (and this has been partially confirmed
> by a result due to Artemov which shows that some "computabiliy version"
> of constructive mathematics (like the so called Markov principle) is
> false in S4Grz (with quantifiers). But intuitionist CTs really asserts
> a different thing. The only roles intuitionistic CTs have in my work
> are for the explanation of why (first person) machine find so hard to
> say yes to the doctor and also to clarify the non-constuctivity feature
> of the "OR" in "Washington OR Moscow" self-duplication experiments.
> Godel did miss Church thesis, and he takes some years for him to
> eventually assess it and then to describe it as a "sort of
> epistemological miracle". At the same time I would say Godel never got
> it completely because he will search for an equivalent miracle for the
> provability notion, but this can be shown being highly not plausible
> ... from Church thesis.
> I have evidence that Charles Babbage (and perhaps its friend Ada
> Lovelace) got Church thesis, once century before the others. The
> evidence comes from a book by Jacques Lafitte(*) who said in 1911 that
> Babbage discovered that his notation system for describing its
> analytical machine was somehow cleverer than his machine. Now, the
> first who really discovered explictly "Church thesis" and its relation
> with both computability and provability, is Emil Post in 1922,
> according to my knowledge.
> Must go now. I intend to comment Tom and Stathis' post later, perhaps
> Saturday because I have exams all the day tomorrow.
> Bruno
> (*) LAFITTE J., 1911, 1932, Réflexions sur la science des machines,
> Vrin 1972 (New Ed.), Paris.

You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at
Received on Sun Jun 18 2006 - 00:36:49 PDT

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