Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!yale!think!samsung!uakari.primate.wisc.edu!ames!amdahl!kp From: kp@uts.amdahl.com (Ken Presting) Newsgroups: comp.ai Subject: Re: Another letter to the New York Review Summary: Peano's Piano - major uncomputability in a physical process Message-ID: <80tJ02UA8cX201@amdahl.uts.amdahl.com> Date: 27 Feb 90 21:34:11 GMT References: <18883@bcsaic.UUCP> <1589@skye.ed.ac.uk> <11488@venera.UUCP> <1754@skye.ed.ac.uk> <90Feb15.231415est.6212@neat.cs.toronto.edu> <2al902Zg8bnn01@amdahl.uts.amdahl.com> <3750@uceng.UC.EDU> ted@nmsu.edu (Ted Dunning) writes: >In article <3750@uceng.UC.EDU> dmocsny@uceng.UC.EDU (daniel mocsny) writes: > > Can any phenomenon be so truly uncomputable that no logical process > could behave equivalently (if not exactly)? > >yes. > >virtually all chaotic dynamical systems have the characteristic of a >computational horizon beyond which any particular computer cannot keep >up with the physical system in doing the simulation. > >the reason for this is that sensitive dependence on initial conditions >requires that the arithmetic that needs to be done gets harder and >harder to do fast enough to keep up with real time. before too long, >you have a system which requires a computer larger than the entire >universe to predict. This is not uncomputable enough. Suppose that one day we find an old piano. On the keys are digits, arithmetic operations + - * / **, parentheses, quantifiers, and "x". The piano makes no sound for any individual keystroke, but we observe that if we play "1+1=2", then close the cover, it sounds a major chord, while if we play "1+1=3" it sounds a minor chord. Playing for a while, we can soon convince ourselves of the proper notation (it makes no sound if we play "1+1=+", plays a major chord for "(x1) 2*x1=x1+x1", etc). Consider the hypothesis that this piano will sound a major chord for every true sentence, and a minor chord for every false one. Clearly, we could never build a machine on purpose, guaranteed to play correctly - that would contradict Goedel's theorem. For similar reasons, no matter how long we observe it, or how carefully we examine its inner workings, we could never prove to ourselves that it is reliable. If we could figure out how & why it worked, we would have an algorithm for deciding truth, another contradiction. Most important, such a device could absolutely never be simulated by a computer. If anybody can think of a physical or logical reason why such a device *cannot* exist, I'd be very interested. I think that Penrose' arguments may reduce to the assertion that such a device is not disallowed by the laws of physics.