Xref: utzoo talk.religion.misc:7918 comp.ai:2323
Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!ukma!gatech!ncsuvx!mcnc!duke!romeo!nlt
From: nlt@romeo.cs.duke.edu (N. L. Tinkham)
Newsgroups: talk.religion.misc,comp.ai
Subject: Re: The Ignorant assumption
Summary: Clarification of "naturally regarded as computable".
Message-ID: <12542@duke.cs.duke.edu>
Date: 1 Oct 88 04:36:59 GMT
References: <1369@garth.UUCP> <2346@uhccux.uhcc.hawaii.edu> <1383@garth.UUCP> <7202@aw.sei.cmu.edu>
Sender: news@duke.cs.duke.edu
Followup-To: comp.ai
Lines: 31


     I have no objection to the formulation "any function that would naturally
be regarded as computable can be computed by a universal Turing machine", as
long as it is clear that being "naturally...regarded as computable" includes
the list of conditions associated with algorithms.  Setting aside those
conditions would introduce a broader definition of "computable" than is in
common use; such a definition may well be interesting to consider, but it might
reduce confusion to use a different term (say, "q-computable").

     The claim that "a function is surely 'computable' if a physical system
can be constructed that computes it" is the disputed point.  In order to
believe that a function f is computable, I will require that I be shown that
there is an algorithm by which f may be computed.  This algorithm need not be
a Turing-machine program (if that were the case, the thesis would indeed be
trivial), but it should conform to the general requirements of an algorithm:
ability to be specified in a description of finite length, computation in
discrete steps, and so forth.  And one of these requirements is that the
computation should not use random methods.  (Reference, again, is to chapter 1
of Rogers' text.

     Falsifying the Church-Turing thesis would require presenting a function f
for which such an algorithm exists, and then showing that f cannot be computed
on a Turing machine.


[We have drifted quite far from religion here.  Followups are directed to
 comp.ai.]

                                            Nancy Tinkham
                                            {decvax,rutgers}!mcnc!duke!nlt
                                            nlt@cs.duke.edu