Date: Mon 10 Oct 1988 15:38-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 #99 To: AIList@AI.AI.MIT.EDU Status: RO AIList Digest Tuesday, 11 Oct 1988 Volume 8 : Issue 99 Mathematics and Logic - The Ignorant assumption (6 messages) ---------------------------------------------------------------------- Date: 16 Sep 88 01:58:53 GMT From: garth!smryan@unix.sri.com (Steven Ryan) Subject: Re: The Ignorant assumption >" ... We all know (I hope) formal systems are either >" incomplete or inconsistent. > >I don't know that. Can you show this for predicate logic? Either a system is too simple (like propositional calculus) to do number theory (which is equivalent to everything else) or it's powerful enough in which Godel's theorem come into play: any system powerful enough for number theory is either incomplete or omega-inconsistent. Simple systems like propositional calculus are complete within their domain, but their domain is incomplete with respect to number theory and all other formal system. (Predicate calculus includes quantifiers; propositional calculus does not.) ------------------------------ Date: 26 Sep 88 23:09:07 GMT From: grad3!nlt@cs.duke.edu (Nancy L. Tinkham) Subject: Re: The Ignorant assumption Robert Firth offers the following proposed refutation of the Church-Turing thesis: > The conjecture is almost instantly disprovable: no Turing > machine can output a true random number, but a physical system can. Since > a function is surely "computable" if a physical system can be constructed > that computes it, the existence of true random-number generators directly > disproves the Church-Turing conjecture. The claim of the Church-Turing thesis is that the class of functions computable by a Turing machine corresponds exactly to the class of functions which can be computed by some algorithm. The notion of an algorithm is a somewhat informal one, but it includes the requirement that the computation be "carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers, _Theory of Recursive Functions and Effective Computability_, p.2). If it is demonstrated that a physical system, by using randomness, can generate the input-output pairs of a function which cannot be computed by a Turing machine, we have merely shown that there exists a non-Turing-computable function whose output can be generated by non-algorithmic means -- hardly surprising, and not relevant to the Church-Turing thesis. Nancy Tinkham {decvax,rutgers}!mcnc!duke!nlt nlt@cs.duke.edu ------------------------------ Date: 27 Sep 88 15:07:41 GMT From: firth@sei.cmu.edu (Robert Firth) Subject: Re: The Ignorant assumption In a previous article, Nancy L. Tinkham writes: > The claim of the Church-Turing thesis is that the class of functions >computable by a Turing machine corresponds exactly to the class of functions >which can be computed by some algorithm. No it isn't. The claim is that every function "which would naturally be regarded as computable" can be computed by a Turing machine. At least, that's what Turing claimed, and he should know. [A M Turing, Proc London Math Soc 2, vol 442 p 230] ------------------------------ Date: 28 Sep 88 05:45:56 GMT From: bbn.com!aboulang@bbn.com (Albert Boulanger) Subject: Re: The Ignorant assumption In <13763@mimsy.UUCP> Darren F. Provine writes You see, ``every function "which would naturally be regarded as computable"'' and ``the class of functions which can be computed by some algorithm'' are pretty much the same thing. Do you have some way of computing a function without an algorithm that nobody else in the entire world knows about? Yup, Quantum Computers! (Half Serious :-)) Let me quote the abstract of the following paper: "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer", D. Deutsch, Proc. R. Soc. Lond. A400 97-117 (1985) "It is argued that underlying the Church-Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: 'every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means'. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and is shown that quantum theory an the 'universal quantum computer' are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive Functions, but they do include 'quantum parallelism', a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett's. (Multiple-Worlds interpretation - ed) Some of the numerous connections between quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the 'complexity' or 'knowledge' in a physical system than does classical complexity theory." For 1 one page description of this paper, see John Maddox's News and Views "Towards the Quantum Computer?", Nature Vol 316, 15 August 1985, 573. For a perspective and a readable account of why Deutsch reasons that universal quantum computers support the Many-Worlds interpretation of Quantum Mechanics, see the chapter on Deutsch in the book, "The Ghost in the Atom", P.C.W. Davies, & J.R. Brown eds, Cambridge University Press, 1986 (Chapter 6). I should also mention that thinking along these lines have led others to investigate the ultimate randomness in quantum mechanics. See "Randomness in Quantum Mechanics - Nature's Ultimate Cryptogram?", T. Erber & S. Putterman, Nature, Vol 317, 7 Nov. 1985, 41-43. Since this report, they have actually analyzed data from NBS ionic-trap data, and so far QM checks out to be really random. Now to some, this stuff about quantum computers may sound MAX flaky, but consider the fact that intuitive people like Feynman wrote papers on the topic. A key new theory that helps put the question of randomness and the question of determinism (to some extent) into perspective is algorithmic complexity theory. In this theory, one can assign a measure of randomness to a number string, by using as a metric the shortest algorithm that could produce that string. If one considers the decimal expansion of the reals, than "most" of the the number line is dominated by numbers with infinite algorithmic complexity. Furthermore, these numbers are inaccessible in any way to "classical" Turing machines in finite time or space. By the way, Erber & Putterman point out in their paper that "the axiomatic development (of QM) is deliberately silent concerning any requirements that the measurable functions be non-determinate or that the elements of probability space correspond to inherently unpredictable or erratic events." The way I think of nondeterminism is operational. For example, if I were to be given an infinite-complexity number like Chaitin's omega, and an infinite resource universal computer I could use it as a seed to a random number generator (ie a chaotic system) and generate truly non-repeating random numbers. But since the initial seed required infinite resources, I could never realize it on a 'classical' computer. The important question is whether nature has access to such numbers. Albert Boulanger aboulanger@bbn.com BBN Systems & Technologies, Inc. ------------------------------ Date: 29 Sep 88 14:51:41 GMT From: firth@sei.cmu.edu (Robert Firth) Subject: Re: The Ignorant assumption Somehow, I get the feeling that our machines are better at forward chaining than we are. Please let me run this Turing machine stuff by you once again. (Translation: this post says nothing new, merely recapitulates.) ---- The question that originally prompted me to speak was this one [ <388@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe)] >But is there any reason to suppose that the universe _is_ a Turing machine? As I understood it, the question referred to the physical world, as imperfectly revealed to us by science, and so I replied [ <7059@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) ] >None whatever. The conjecture is almost instantly disprovable: no Turing >machine can output a true random number, but a physical system can. 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. Now, it is not my job to supply an "algorithm" for this function: as the physicist I have given you a specification and a model implementation; as the computer scientist it is your job to give me an equivelent program. However, being a kind-hearted soul, I shall point you to an algorithm; it is given as equation (3.1) in the paper [Deutsch: Proc Roy Soc A vol 400 pp 97-117] Naturally, it uses primitive operations that you won't find in a classical computing engine, which is why the title reads "Quantum theory, the Church-Turing principle, and the universal quantum computer". Turning now to that "principle": The formulation I learned was, briefly, that any function that would naturally be regarded as computible can be computed by a universal Turing machine. Once again, I made my opinion on this absolutely clear [art. cit.]: 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. For example, one could stipulate A function is to be regarded as computable only if it can be described by an algorithm written in a programming language implementable on a universal Turing machine. In which case, the conjecture becomes vacuously true, and the discipline of AI becomes vacuously futile. For the point of "artificial intelligence", surely, is accurately to reproduce, in some computing engine, the behaviour of certain physical systems, especially those that show goal- directed behaviour, judgement, creativity, or whatever else one means by "intelligence". If this is to be remotely feasible, then the model of the computation process must be at least general enough to embrace the known basic operational features of physical systems. After all, if your programming tools cannot reproduce so simple a physical system as my random Boolean generator, the chance of their being able to reproduce a complicated physical system - the brain of a flatworm, for instance - must be very close to zero. Robert Firth ------------------------------ Date: 30 Sep 88 01:31:58 GMT From: nau@mimsy.umd.edu (Dana S. Nau) Subject: Re: The Ignorant assumption In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: < ... 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. As far as I can see, what you have defined is not a function. A function is normally defined to be a set F of ordered pairs (x,y) such that for each x, there is at most one y such that (x,y) is in F (and this y we normally call F(x)). Until all of the ordered pairs that comprise F have been unambiguously determined, you have not defined a function. Note that this does NOT mean that you have to tell us what all of the ordered pairs are or how to compute them, or that you know what they are, or that it is even possible to compute them (for some interesting examples, see page 9 of Hartley Rogers' book, "Theory of Recursive Functions and Effective Computability). It just means that it must be unambiguous what they are. If your mapping "|" is a function, then it must be one of the following: | = {(0.0), (1,0)} | = {(0.0), (1,1)} | = {(0.1), (1,0)} | = {(0.1), (1,1)} If it were unambiguous WHICH function "|" was, then "|" WOULD be Turing-computable. In fact, it would even be primitive recursive. But if we assume that the output of your box is truly random, then your definition leaves it indeterminate which of the above functions "|" actually is. Thus, as a function, "|" is ill-defined. < ... The formulation I learned was, briefly, < that any function that would naturally be regarded as computible can be < computed by a universal Turing machine. Once again, I made my opinion < on this absolutely clear [art. cit.]: < < 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. I disagree. The point of my above argument is that true random-number generators do not satisfy the definition of a function, so the theory of Turing computability does not apply to them. Just one other point, to avoid possible confusion: A random variable IS normally defined as a function. However, it is not a function such as "|", but is instead the function which maps the sample space of a random experiment into the set of real numbers. In your example, the sample space is the set {0,1}, so to map this into the set of real numbers you can simply use the identity function. -- Dana S. Nau ARPA & CSNet: nau@mimsy.umd.edu Computer Sci. Dept., U. of Maryland UUCP: ...!{allegra,uunet}!mimsy!nau College Park, MD 20742 Telephone: (301) 454-7932 ------------------------------ End of AIList Digest ********************