"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/?member_id=8660244&id_secret=106510220-47b225 Powered by Listbox: http://www.listbox.com
