Re: Turing vs math

From: Marchal <>
Date: Mon Oct 25 02:31:11 1999

Hal finney wrote:

>There are other ways to formalize computing: stack machines, register
>machines, cellular automata, even idealized billiard balls bouncing
>around in a giant pinball machine. Each one agrees with the others on
>computational complexity, but again only up to a "scale factor" which
>includes the additive constant.

I'm afraid this is false. Although Quantum Computing does not
violate Church's Thesis. It does violate the complexity-restriction
of it. It is true that all classical computers can emulate each
other in polynomial time, but there are strong evidences that
quantum computer cannot be emulate by classical computer without
an exponential slow-down.
This can be a fundamental point in our search of the measure.
But in my approach I cannot postulate a quantum world, I must derive
it from abstract computability.

... and this happens with the logic Z1* ...
(chapter 5 of

Received on Mon Oct 25 1999 - 02:31:11 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:06 PST