Xref: utzoo comp.ai:6164 sci.philosophy.tech:2188 Path: utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!brutus.cs.uiuc.edu!apple!amdahl!kp From: kp@uts.amdahl.com (Ken Presting) Newsgroups: comp.ai,sci.philosophy.tech Subject: Re: Another letter to the New York Review Summary: You can skip this one, it's just more philosophical pedantry Keywords: Penrose, Moravec Message-ID: <05HI02Xt8fJC01@amdahl.uts.amdahl.com> Date: 6 Mar 90 18:33:44 GMT References: <18883@bcsaic.UUCP> <1589@skye.ed.ac.uk> <11488@venera.UUCP>1754@skye.ed.ac.uk> < Reply-To: kp@amdahl.uts.amdahl.com (Ken Presting) Organization: Amdahl Corporation, Sunnyvale CA Lines: 125 In article <90Mar3.152728est.6160@neat.cs.toronto.edu> radford@ai.toronto.edu (Radford Neal) writes: >> . . . Of course, computers are entirely >>adequate to implement deductive systems, by the Church-Turing thesis. > >I think you're suffering from a lack of imagination here. . . . Them's fightin' words. >Let's say that one day Penrose announces that he is able to solve, say, >the word problem for semi-groups - a well-known non-computable problem. >People give him instances of this problem. After a period of time >that goes up only reasonably with the size of the instance he announces >the answer: YES or NO. In those cases where the true answer is >subsequently determined, he always turns out to be right. This holds >even for very difficult cases that require increasingly subtle >arguments to establish that the answer is NO, as well as cases where >extremely complex reductions are needed to demonstrate that the answer >is YES. If you drop the restriction that the computing device (wet or dry) be constructed on purpose, the trap door swings both ways. My feeble imagination can picture a computer pre-programmed with any number of Y's & N's, (of course I can't imagine how) just waiting to pop out when a word problem gets typed in. Urrrnnnh. (Ouch!) Seriously straining my simplistic cerebrum, I can even imagine sooo many little y's and n's mashed into memory that the only word problems the machine couldn't "solve" are sooo long that nobody could type them in in a lifetime. (Picture all the little y's and n's packed into a Penrose tiling of main storage. Don't ask me how they got that way.) And that's the best I can do. I put in the original argument that the period for testing the simulation output would have to be finite. That was on purpose. I tell you, that argument has more spin than a whole flock of Fermions. > . . . You could construct >a similar scenario in which the word problem is solved by some physical >computer (obviously not Turing equivalent), rather than by a human being. Funny you should mention that: >From: kp@uts.amdahl.com (Ken Presting) >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 > >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. (Note: My construction explicitly assumes that the device is not bounded in the range of inputs for which it is successful) Of course, I wrote this before I strained my imagination on Penrose tiles. It was also before that unfortunate accident that I stumbled on a partial answer. Ted Dunning's comment on machines that can store a real number got me thinking. Sure, a real number can encode an infinite sequence in its decimal expansion: instant Entsheidungsantwort. But that is not just an infinite amount of information, it's a *non-denumerable* amount of information. Now, a real physical device is made of finitely many atoms, each with a *denumerable* infinity of orbitals. That makes only denumerably many states, and therefore a denumerable amount of information in any one state. So, if you want to encode the answer to the EP, you'll have to do so in some other set of states than the electron orbitals, the nuleon orbitals, molecular vibration modes, et al. (Assuming, of course, that all particles in the machine are in bound states. Tunneling would lose information, when it occurs, so I'll ignore it). Now, "who ya gonna call?". It's hard enough to read anything out of the outer orbital states. Since the difference in energy between levels decreases without limit, the time required to measure the energy level of an excited electron (say) with sufficient accuracy to distinguish between adjacent levels will increase without limit. (Assuming that all those excited 'trons stay put long enough to make the machine useful. Most likely, you'd get one big white flash. Bigger, if you used excited nuclear states.) What's left? Store data in hidden variables? Call Ghostbusters - there's a ghost in that machine... ****** Radford, I hope you found this article both informative and amusing. I do not feel that I have the luxury of offending anyone who is willing to take the time to read and respond to my ideas. But I do enjoy exercising my imagination. :-) Ken Presting (Wait; what's that still small voice? What's that? "Dyyynaamiic Prooocessseeeesss... Dddyyynnnaammiicc Pprroocceesseess..." All right, all right, I haven't considered the possibility of storing information in dynamic processes. Wait for my imagination to recover, and I'll post again.)