Re: The Future of Chess and Getting It "Unstuck"

I think I am off-topic, but it isn't completely clear whether Church's
thesis is supposed to apply to analog machines. It is even less clear
when you bring in the notion of time complexity. There are some NP-
complete problems which can be solved in polynomial time on analog
machines, but some other parameter always seems to become exponential.
I believe that Stieglitz and Vergos made a separate "thesis" to deal
with this issue. I may be a crackpot, but I think that perhaps someday
some Einstein will figure out a relation between the time to solve a
problem on a digital machine and other parameters, like the force you
need to stomp on a lever to solve a problem on an analog machine
(there is a polynomial time algorithm to solve CNF-satisfiability on a
polynomial size machine built with levers, but you need to stomp on
the lever with exponential force!) Weird stuff.

Jerry Spinrad

On Apr 19, 1:23=A0pm, David Richerby <dav...@[EMAIL PROTECTED]
>
wrote:
> Guy Macon <http://www.guymacon.com/>
wrote:
> > The above quote doesn't say that a Turing machine cannot simulate
> > a Quantum Computer, only that it cannot do so in an efficient way,
> > which is what I originally wrote. =A0Do you have a quote sup****ting
> > your claim that a Turing machine cannot simulate all computers?
>
> Define `computer'. =A0It's pretty hard to avoid implicitly taking the
> Church-Turing thesis as being, in effect, the definition of `computer'
> or `algorithm'.
>
> Dave.
>
> --
> David Richerby =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
=A0Brok=
en Generic Drink (TM): it'swww.chiark.greenend.org.uk/~davidr/=A0 =A0 =A0
li=
ke a refre****ng juice beverage but
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
=
=A0 =A0 =A0 it's just like all the others and it
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0
=
=A0 =A0 =A0 doesn't work!