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