The standard model of quantum computation as defined by Feynman and Deutsch is Turing computable (based on the concept of qubits). As proven by Deutsch they compute the same set of functions than Turing machines but faster (if they are feasible).
Non-standard models of quantum computation are not widely accepted, and even when they could hypercompute many doubt that we could take any from continuum entangling to perform computations. Non-standard quantum computers have not yet being well defined (and that is one of the many issues of hypercomputation: each time one comes up with a standard model of hypercomputation there is always another not equivalent model of hypercomputation that computes a different set of functions, i.e. there is no convergence in models unlike what happened when digital computation was characterized). Hypercomputational models basically pretend to take advantage from either infinite time or infinite space (including models such as infinite resources, Zeno machines or the Omega-rule, real computation, etc.), from the continuum. Depending of the density of that space/time continuum one can think of several models taking advantage at several levels of the arithmetical hierarchy. But even if there is infinite space or time another issue is how to verify a hypercomputation. One would need another hypercomputer to verify the first and then trust in one. Whether you think hypercomputation, the following paper is a most read for those interested on the topic. Martin Davis' articulates several criticisms: The myth of hypercomputation, in: C. Teuscher (Ed.), Alan Turing: Life and Legacy of a Great Thinker (2004) Serious work on analogous computation can be found in papers from Felix Costa et al.: http://fgc.math.ist.utl.pt/jfc.htm My master's thesis was on the subject so if you are interested in getting an electronic copy just let me know. It is in French though. On Wed, Jul 2, 2008 at 11:15 AM, Abram Demski <[EMAIL PROTECTED]> wrote: > "So yes, I think there are perfectly fine, rather simple > definitions for computing machines that can (it seems > like) perform calculations that turing machines cannot. > It should really be noted that quantum computers fall > into this class." > > This is very interesting. Previously, I had heard (but not from a > definitive source) that quantum computers could compute in principle > only what a Turing machine could compute, but could do it much more > efficiently (something like the square root of the effort a Turing > machine would need, at least for some tasks). Can you cite any source > on this? > > But I should emphasize that what I am really interested in is > computable approximation of uncomputable things. My stance is that an > AGI should be able to reason about uncomputable concepts in a coherent > manner (like we can), not that it needs to be able to actually compute > them (which we can't). > > On Tue, Jul 1, 2008 at 2:35 AM, Linas Vepstas <[EMAIL PROTECTED]> wrote: >> 2008/6/16 Abram Demski <[EMAIL PROTECTED]>: >>> I previously posted here claiming that the human mind (and therefore >>> an ideal AGI) entertains uncomputable models, counter to the >>> AIXI/Solomonoff model. There was little enthusiasm about this idea. :) >> >> I missed your earlier posts. However, I believe that there >> are models of computation can compute things that turing >> machines cannot, and that this is not arcane, just not widely >> known or studied. Here is a quick sketch: >> >> Topological finite automata, or geometric finite automata, >> (of which the quantum finite automata is a special case) >> generalize the notion of non-deterministic finite automata >> by replacing its powerset of states with a general topological >> or geometric space (complex projective space in the quantum >> case). It is important to note that these general spaces are >> in general uncountable (have the cardinality of the continuum). >> >> It is "well known" that the languages accepted by quantum >> finite automata are not regular languages, they are "bigger" >> and "more complex" in some ways. I am not sure what is >> known about the languages accepted by quantum push-down >> automata, but intuitively these are "clearly" different (and bigger) >> than the class of context-free languages. >> >> I believe the concepts of topological finite automata extend >> just fine to a generalization of turing machines, but I also >> believe this is a poorly-explored area of mathematics. >> I beleive such machines can compute things that turing >> machiens can't .. this should not be a surprise, since, >> after all, these systems have, in general, an uncountably >> infinite number of internal states (cardinality of the >> continuum!), and (as a side effect of the definition), >> perform infinite-precision addition and multiplication >> in finite time. >> >> So yes, I think there are perfectly fine, rather simple >> definitions for computing machines that can (it seems >> like) perform calculations that turing machines cannot. >> It should really be noted that quantum computers fall >> into this class. >> >> Considerably more confusing is the relationship of >> such machines (and the languages they accept) to >> lambda calculus, or first-order (or higher-order) logic. >> This is where the rubber hits the road, and even for >> the simplest examples, the systems are poorly >> understood, or not even studied. So, yeah, I think >> there's plenty of room for "the uncomputable" in >> some rather simple mathematical models of generalized >> computation. >> >> --linas >> >> >> ------------------------------------------- >> agi >> Archives: http://www.listbox.com/member/archive/303/=now >> RSS Feed: http://www.listbox.com/member/archive/rss/303/ >> Modify Your Subscription: http://www.listbox.com/member/?&; >> Powered by Listbox: http://www.listbox.com >> > > > ------------------------------------------- > agi > Archives: http://www.listbox.com/member/archive/303/=now > RSS Feed: http://www.listbox.com/member/archive/rss/303/ > Modify Your Subscription: http://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com > -- Hector Zenil http://zenil.mathrix.org ------------------------------------------- agi Archives: http://www.listbox.com/member/archive/303/=now RSS Feed: http://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: http://www.listbox.com/member/?member_id=8660244&id_secret=106510220-47b225 Powered by Listbox: http://www.listbox.com
