He points out that this algorithm can be implemented on an analog computer , but " do not worry: more subtle uses of quantum interference cannot be explained away so easily with classical thinking. " The Church - Turing Thesis says that the meaning of " effective computation " is equivalent to " all computations that can be performed by a Universal Turing Machine " . Church 's Thesis says that the meaning of " effective computation " is equivalent to " all computations that can be programmed in Church 's lambda calculus " . The BlumShubSmale model is constructed over any ring , including both integers and reals .

A summary of the physical basis of quantum computation appeared last week in " Science " magazine . In it David Vencenzo points out that " It is evident from this survey of the current state of the art in quantum experimental physics that the construction of quantum computers is presently in the most rudimentary stage , and that to even think about a procedure like Shor factorization , which might require millions of operations on thousands of qubits , might be absurdly premature .

Nevertheless , there are some useful things to think about in quantum computation from the perspective of the construction of consciousness . A year ago , Gilles Brassard wrote a short note in SIGACT News where he showed an algorithm for the " square root of NOT " - - a function QCF such that QCF ( QCF ( |0> ) ) = |1> and QCF ( QCF ( |1> ) ) = |0> when you let |1> mean TRUE and |0> mean FALSE .

He points out that this algorithm can be implemented on an analog computer , but " do not worry: more subtle uses of quantum interference cannot be explained away so easily with classical thinking. "

Now the square root of NOT is well and good , but what we really need is a " square root of Lambda " .

It 's important in this context to distinguish between Church 's Thesis and the Church - Turing Thesis . The Church - Turing Thesis says that the meaning of " effective computation " is equivalent to " all computations that can be performed by a Universal Turing Machine " . Church 's Thesis says that the meaning of " effective computation " is equivalent to " all computations that can be programmed in Church 's lambda calculus " . The equivalence of the lambda calculus and a UTM is generally assumed to be obvious , but it 's not actually true . A UTM is a finite - state machine plus a tape with a countable infinity of cells , each cell containing a finite set of symbols . The lambda calculus , however , in its most popular form with mathematicians , is type - free , able to operate on any set , even uncountable infinities .

---

Put this together with the fact , which goes without saying among physicists , that quantum states , even *after* the reduction of the wavefunction , are continuous values , i.e. sets with an uncountable infinity of values , and you have some interesting consequences .

---

First of all , even before quantum interference , you get important consequences for computational complexity and unsolvability , as Newton and Leibniz showed when they used differential calculus to resolve the famous paradoxes of Zeno of Elea . Zeno 's theory of computation used discrete time and continuous space much like the one of Blum , Shub and Smale ( 1989 ) to show , among other things , that " motion is impossible. " With differential calculus you show how the limit of certain infinite series are bounded , and that a computation that may not halt in the Turing model if the target of Zeno 's arrow happens to be located " between the cracks in the rationals " on a location with an irrational value in the coordinate space , will halt if variables can be real - valued . The BlumShubSmale model is constructed over any ring , including both integers and reals .

---

Actually , Zeno was using a more powerful model than BlumShubSmale , in which the computation steps run faster as time goes by . This model is discussed briefly by Boolos and Jeffrey ( 1980 ) who call it the Zeus machine . I 've been unable to find any discussion in the literature of a universal theory of computation in the continuous , Newtonian time that is used by classical analog computers .

---

Yet in quantum theory , even time is quantized , so a universal theory of continuum computation implement in classical physics might have power superior to a quantum computer . Quantum theory , on the other hand , provides properties of superposition and interference that may lead to greater computational power that pure continuum systems . Or it may not . I 'm inclined to think that their scopes will be different , neither one a superset of the other .

---

Do not be taken in by blanket statements of computability or uncomputability . As Rogers ( 1987 ) discusses in great detail , there are many kinds and levels of uncomputability . Penrose ( 1994 ) argues that his perception of mathematical truth is beyond any level of computability , even an infinite tower of Oracle Machines . He simply misunderstands the function of oracles in computation theory . I use his argument to apply Penrose 's own book as an input to his infinite tower of Oracle Machines and thereby show that my mathematical perception is superior to anything he may write . Where his book contradicts my perception of mathematical truth ( which it does in innumerable ways ) then his book and its Oracle argument is unargubly wrong . If his book is right and I 'm wrong , then Oracle Machines must be able to capture absolutely any computation and his argument is still wrong .

---

How could we approach a theory of quantum computability as an extension of Turing computability theory ? One way is to insert uncountable sets using the BlumShubSmale model as a first step . We could then relax the assumption of discrete time and treat the UTM as a dynamical system operating in continuous time , attempting to define a Universal Dynamical System that somehow represents a description of other dynamical systems in its state space , and proceeds in time by following that definition , producing identical behavior to a system implementing the definition directly . We could finally attempt to show that quantum theory defines a particular UDS that , among other properties , includes an equivalence class of physically realizable UTMs .

---

Another route would be to follow the " square root of lambda " idea , analogizing the development of recursive function theory with the development of mathematics , where the idea of the square root required the introduction of irrational numbers . Quantum superposition of computations can be described as a superposition of partially evaluated functions , with interference prohibiting some solutions and permitting others . What happens when the partially evaluated function is a functional form , instead of a simple function ? Is ( lambda X ( halts X ) ) in the computability class where this works ? I think not , but there may be other Turing - uncomputable functions where it does work .

Until we 've seen a development along one of these routes , I think it 's safe to say that while the Church - Turing Thesis may be problematic , Church 's Thesis still holds , and that computers can do anything that is clearly and precisely describable , including support conscious systems . Theories that claim otherwise are distinguishable by the amount of handwaving and magic they involve , and should not be promoted as convincing .

---