Date: Mon 10 Oct 1988 15:41-EDT From: AIList Moderator Nick Papadakis Reply-To: AIList@AI.AI.MIT.EDU Us-Mail: MIT LCS, 545 Tech Square, Rm# NE43-504, Cambridge MA 02139 Phone: (617) 253-6524 Subject: AIList Digest V8 #100 To: AIList@AI.AI.MIT.EDU Status: RO AIList Digest Tuesday, 11 Oct 1988 Volume 8 : Issue 100 More on ... The Ignorant assumption (6 messages) ---------------------------------------------------------------------- Date: 30 Sep 88 07:51:15 GMT From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Re: The Ignorant assumption In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: > Since a function is surely "computable" if a physical ******** > system can be constructed that computes it, ... >from which, I submit, the conclusion follows: > ... the existence of true random-number generators directly > disproves the Church-Turing conjecture. >Granted, one can readily evade this conclusion. It is necessary merely >to redefine "natural", "computable", "function", or some other key term. It is not necessary to REdefine "function", only to use the usual meaning. Given the same inputs, a function must always yield the same output(s). The kind of physical system Firth has described is a realisation of a(n indexed) random variable, and it has been held for many years that "true random numbers" are not computable. (See section 3.5 ("What is a random sequence") of Knuth's "The Art of Computer Programming, Vol 2", this statement is implicit in definition R6. The original question was a purely rhetorical one (I _don't_ believe that the universe is a Turing machine), but it's worth pointing out that we only have a finite set of imprecise observations, so that a sufficiently good simulation of a quantum-mechanical system (with top-notch pseudo- random number generation!) *might* be fooling us. You can only appeal to phsyical random number generators to disprove the Church-Turing hypothesis if you assume that the quantum-mechanical laws a really true, which is to say if you already assume that the universe is not running on a Turing machine. I believe it, but a circular "proof" like that is no proof! ------------------------------ Date: 30 Sep 88 14:00:44 GMT From: uhccux!lee@humu.nosc.mil (Greg Lee) Subject: Re: The Ignorant assumption >From article <13791@mimsy.UUCP>, by nau@mimsy.UUCP (Dana S. Nau): " In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: " ... " < of as a mapping " < " < {0,1} => 0|1 " ... " As far as I can see, what you have defined is not a function. A function is There are a couple (>=2) of things I don't understand about this discussion: Why does it matter whether Turing machines compute functions? If one wants to compute non-functional relations, why not just define the machines accordingly? If there's a terminological problem, then call the machines something else. What does it matter to Church's thesis whether what is computed is a function? Sometimes the thesis is phrased using the word function, but is that essential to the thesis? And anyhow, why can't `0|1' be considered a single value? Greg, lee@uhccux.uhcc.hawaii.edu ------------------------------ Date: 30 Sep 88 20:34:32 GMT From: garth!smryan@unix.sri.com (Steven Ryan) Subject: Re: The Ignorant assumption >random number generation!) *might* be fooling us. You can only appeal to >phsyical random number generators to disprove the Church-Turing hypothesis >if you assume that the quantum-mechanical laws a really true, which is to >say if you already assume that the universe is not running on a Turing machine. >I believe it, but a circular "proof" like that is no proof! Well, just to keep things straight, I'm the one who mentionned TM and CT. I used them as a conditionals, `If the universe was a TM, then such and such would follow.' It wasn't intended to assert, prove, or disprove CT, but just engage in withywanderring philosophical speculation. To me, the Ignorant Assumption is not any particular theory or religion, but the meta-assumption that assumptions are unnecessary. ------------------------------ Date: 1 Oct 88 04:36:59 GMT From: romeo!nlt@cs.duke.edu (N. L. Tinkham) Subject: Re: The Ignorant assumption 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 ------------------------------ Date: 3 Oct 88 05:18:16 GMT From: vax5!w25y@cu-arpa.cs.cornell.edu Subject: Re: The Ignorant assumption The Church-Turing thesis deals with relations that always give the same output value for a given input value. Any quantum-generated random function would not have this property. -- Paul Ciszek W25Y@CRNLVAX5 Bitnet W25Y@VAX5.CCS.CORNELL.EDU Internet ------------------------------ Date: 5 Oct 88 15:31:43 GMT From: shire!ian@psuvax1.psu.edu (Ian Parberry) Subject: Ignorance about the ignorant assumption In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: >To elaborate: I can build a box, whose main constituents are a supply >of photons and a half-silvered mirrir, that, when triggered, will emit >at random either the value "0" or the value "1". This can be thought >of as a mapping > > {0,1} => 0|1 > >where I introduce "|" to designate the operator that arbitrarily selects >one of its operands. The obvious generalisation of this - the function >that selects an arbitrary member of an input set - is surely not unfamiliar. > >Nobody has denied that a Turing machine can't do this. The assertion that >a physical system can do it rests on the quantum theory; in particular on >the proposition that the indeterminacy this theory ascribes to the >physical world is irreducible. Since every attempt to build an alternative >deterministic theory has foundered, and no prediction of the quantum theory >has yet been falsified, this rests on pretty strong ground. Have I missed something here? Theoretical Computer Scientists have been stepping beyond the bounds of the Church-Turing thesis for years. The obvious question which was first asked a long time ago (I believe that Michael Rabin was amongst the first to do so) is whether the kind of randomness described above helps computation. An obvious answer is that it sometimes helps speed things up. For example, there are several polynomial time probabilistic primality testing algorithms, but no deterministic one is known (although it must be admitted that one exists if the Riemann Hypothesis is true). The Church-Turing thesis is not and never has been a sacred cow amongst Theoretical Computer Scientists. Most view it as a handy rule of thumb, and nothing else. It's not hard to invent machines which violate the Church-Turing thesis. The hard part is developing a non-trivial, entertaining, elegant and useful theory of computation around them. My favourite work of this kind is on non-uniform circuit complexity. Curiously, many lower-bounds proved to date hold for non-uniform (read non-Church-Turing- thesis) circuits, and have matching uniform (read Church-Turing-thesis) upper-bounds. Most of the postings I've seen to date have been from non-TCS people. However, since the Church-Turing thesis is a part of Theoretical Computer Science, it is worth finding out what the TCS'ers have had to say about it. For a ton of reading, look for articles that mention the key words probabilistic algorithm, RP, BPP, RNC in the proceedings from the IEEE Symposium on Foundations of Computer Science and the ACM Symposium on the Theory of Computing for the last decade. For more polished but less up-to-date material, consult theory journals such as SIAM J. Computing, Journal of the ACM, Theoretical Computer Science, Journal of Computer and System Sciences, Journal of Algorithms, Information Processing Letters. Of course, I'm not saying that Theoretical Computer Scientists have all of the answers. But they do seem to have made a good try at addressing the obvious questions. ------------------------------------------------------------------------------- Ian Parberry "The bureaucracy is expanding to meet the needs of an expanding bureaucracy" ian@psuvax1.cs.psu.edu ian@psuvax1.BITNET ian@psuvax1.UUCP (814) 863-3600 Dept of Comp Sci, 333 Whitmore Lab, Penn State Univ, University Park, Pa 16802 ------------------------------ End of AIList Digest ********************