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