Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ucbvax!umnd-cs!umn-cs!moll
From: moll@umn-cs.UUCP
Newsgroups: sci.philosophy.tech
Subject: Re: Complexity and Philosophy
Message-ID: <1642@umn-cs.UUCP>
Date: Sun, 7-Jun-87 16:16:58 EDT
Article-I.D.: umn-cs.1642
Posted: Sun Jun  7 16:16:58 1987
Date-Received: Tue, 9-Jun-87 00:50:17 EDT
References: <19071@ucbvax.BERKELEY.EDU> <8705291501.AA12310@brahms.Berkeley.EDU> <634@uwm-cs.UUCP>
Reply-To: moll@umn-cs.UUCP (Rick Moll)
Distribution: world
Organization: University of Minnesota
Lines: 34
Keywords: Church's thesis, complexity
Summary: Church's thesis not about complexity, Finite fns. quickly computable.

In article <634@uwm-cs.UUCP> litow@uwm-cs.UUCP (Dr. B. Litow) writes:
>is disturbing to me. I should say that I 'sort of' believe it. CS is the
>working out,largely mathematically as in physics,of the consequences of
>assuming Church's Thesis. If some cooperative quantum effect e.g. spin
>glasses can really be used to solve problems in,say PTIME,which have been
>shown (some day) not to be in PTIME,then CT is called into question.

Church's Thesis (also known, I believe, as the Church-Turing thesis) is
the assertion that every "effectively computable" function is computable
by Turing machine.  It says only that anything you can compute in *finite*
time on any machine can be done in *finite* time on a Turning machine.
The TM implementation may take much longer.  The existence of a faster
machine doesn't invalidate the thesis, it would require the existence
of a machine which could compute something in finite time that no TM
can compute in finite time to disprove Church's thesis.

Note: There are many equivalent ways of stating Church's thesis.
Rather than Turing machines, for example, one can use recursive functions
or Lambda calculus.  These forms are, however, provably equivalent.  These
are the only statements I have ever seen referred to as "Church's thesis".
Is there some stronger statement, perhaps referring to speed of computation,
which is also referred to as "Church's thesis"?
 
>one objects that these 'damn fast' computations hold only over a finite range
>of data sizes but I think that there may be theorems of CS which could
>extend 'damn fast' computations over all sizes. 

If I understand what you're saying, then there is no such theorem.  Any
finite segment of any function can be computed "damn fast" simply by
coding a table of values into the program.  There are, however, functions
for which the best machine to compute the *whole* function is "damn slow".

Reference: _Introduction to Automata Theory, Languages and Computation_
by Hopcroft and Ullman.