Yes, I was not claiming that there was just one type of hypercomputer, merely that some initially very different-looking types do turn out to be equivalent.
You seem quite knowledgeable about the subject. Can you recommend any books or papers? On Wed, Jul 2, 2008 at 1:42 PM, Hector Zenil <[EMAIL PROTECTED]> wrote: > On Wed, Jul 2, 2008 at 1:30 PM, Abram Demski <[EMAIL PROTECTED]> wrote: >> Hector Zenil said: >> "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" >> >> This is not entirely true. Turing's oracle machines turn out to >> correspond to infinite-time machines, and both correspond to the >> arithmetical hierarchy. > > At each level of the arithmetical hierarchy there is a universal > oracle machine (a hypercomputer), so there is no standard model of > hypercomputation unless you make strong assumptions, unlike digital > computation. There are even hiperarithmetical machines and as stated > by Post's problem, intermediate non-comparable degrees at each level > of the arithmetical and hiperarithmetical (that's why the Turing > universe does not build a total order). > >> >> On Wed, Jul 2, 2008 at 12:38 PM, Hector Zenil <[EMAIL PROTECTED]> wrote: >>> 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/?&; >>> 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/?&; > 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
