X-Message-Number: 9263 Date: Wed, 11 Mar 1998 10:48:33 -0800 From: Tim Freeman <> Subject: Non-turing computation reference (was Re: CryoNet #9260 - #9261) Thomas Donaldson said: >In discussing the counterexample in depth I am a bit at a temporary handicap >here because I've packed away the issue of NATURE in which it was >presented, and so would have to search for the reference and get the >article some other way One reference is "Computation Beyond the Turing Limit", by Hava Siegelmann, Sience Vol. 268, 28 April 1995, pages 545-548. I have it sitting here in front of me. Basically, Hava assumes that an analog machine can access arbitraily many significant bits of some physical constant. For instance, if we assume that matter is perfectly continuous (hah!) and we can cut a bar of steel so that the i'th bit of the binary representation of its length says whether the i'th Turing Machine halts (hah!), and we can make a device that can eventually find the i'th bit of the length of the bar (hah!), then we have a machine that can solve the halting problem. This assumption is illustrated by the pi-bar in the analog shift map at the beginning of page 547. This stands for the binary representation of pi, with some technical tweaks that don't matter. The point of the paper is that you could do non-Turing computation if you replace the pi in the table with some non-computable number like the length of my steel bar. One constraint in the paper is that the machines must have finite input. They accomplish this by saying that the number pi or the length of the bar is part of the machine, not part of the input. Unfortunately for this scenario, the real world is noisy, and only the finite number of bits that are significant enough not to be swallowed by the noise can really make a non-random contribution to a computation. This argument applies as well to neurons as steel bars. Maybe by making bigger and bigger machines, you could dig down to any arbitrary bit of a universal constant, such as the constant of gravity. So if the (i+100)th bit of the constant of gravity tells us whether the i'th Turing machine halts, then you could construct a physical machine that would construct an experimental apparatus large enough to extract any bit and solve the halting problem, assuming infinite patience (hah!) and an infinite universe (hah!). But I have no reason to believe that there are any surprisingly meaningful messages buried in these universal constants, nor do I have any reason to believe that neurons do this. -- Tim Freeman http://www.infoscreen.com/resume.html Web-centered Java, Perl, and C++ programming in Silicon Valley or offsite Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=9263