Re: Infinite computing
I was wondering, if it's true that Hawking radiation always causes a black hole to evaporate after some finite time, wouldn't that mean that any observer travelling into one will see it evaporate before he crosses the event horizon? Is it possible that quantum gravity could do away with the notion of seeing the entire infinite history of the universe by travelling into a black hole? Jesse Mazer _ MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*. http://join.msn.com/?page=features/virus
Re: Infinite computing: A paper
At 03:21 PM 2/10/2003 -0500, Stephen Paul King wrote: Dear Jean-Michel and Hal, All good humor aside, Hal makes a good point! The conditions that would exist as one approaches the event horizon seem to be such that any signal would be randomized such that the end result would be that Nature prevents infinite information (or conclusions requiring infinite computational power) from reaching any finite part of itself. Interestingly this seems to be the same situation as what forms an event horizon (around a space-time singularity) in the first place. Could it be that this is an active example of the so-called anthropic principle? It also reminds me of a solution to the Quantum Suicide problem! Kindest regards, Stephen Thank you to all of you for your ideas. Let us say that my suggestion was merely provocative. It seems to be that hypercomputers are logically possible, but that it is still speculative whether they are physically possible or not. This is Toby Ord's view in http://arxiv.org/pdf/math.LO/0209332. I find his survey very good. In particular, it contains a reference to Does General relativity Allow an Observer to View an Eternity in a Finite Time ? by Mark L. Hogarth, and to Non-Turing computations via Malament-Hogarth space-times, by Etesi and Németi, http://www.math-inst.hu/pub/algebraic-logic/turing.ps, which will be of interest to many, and especially to Jesse Mazer, as it discusses his question. All the best. Jean-Michel - Original Message - From: Hal Finney [EMAIL PROTECTED] To: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Monday, February 10, 2003 12:19 PM Jean-Michel Veuillen writes: There are other possibilities to obtain hypercomputers or Infinite Time Turing Machines: For instance, from general relativity: put a computer in orbit around a black hole, start an infinite computation on it, arrange that the results are sent to you by radio, and jump into the black hole: when you reach the horizon, you get the result of the infinite computation (and witness the end of the rest of the universe). For a survey: arxiv.org/pdf/math.LO/0209332 ...and burn to death as infinite amounts of radiation fall on you in a finite time? Maybe the universe is like a character from a spy novel: it could tell us what it knows (solving the halting problem, etc.), but then it has to kill us. Hal F.
Re: Infinite computing
Dear George, As I read your post I was struck by the necessary assumptions that you noted: 1) that the black hole is large enough that the tidal forces do not rip apart the observer falling into it2) death occurs in one branch of the multiverse but not in another. What if we considered the case where we used the size (mass) of the black as a parameter to evaluate the communicability of our hypothetical infinite computer? What would be the analogue in the multiverse? I have been re-reading my copy of Bohm and Hiley's The Undivided Universe and in particular the discussion of Gell_Mann and Hartle's consistent histories interpretation and comparison with MWI. It occurs to me that the size of the black hole (a function of its mass) and the differences between a pair of branches of the multiverse (a function of the non-commutability of their associated operators?) both seem to be 3-person notions (borrowing Bruno Marchal's term) while the idea of infinite computing that we are discussing seems to be a 1-person notion. The relation that Hawking et al have written about between a black hole's mass and its entropy seem to be 3-person notions and we seem to be in need of a 1-person analogue. Could it be that the notion of decoherence could be this 1-person analogue? I will be reading the papers that Jean-Michel referenced and dreaming up a thought experiment. Do you have any ideas at this time? Kindest regards, Stephen - Original Message - From: George Levy To: [EMAIL PROTECTED] Sent: Tuesday, February 11, 2003 1:23 AM Subject: Re: Infinite computing Stephen,Amazingly, I had kind-of the same thought. From the point of view of information flow, there seems to be an analogy between 1) falling down into a black hole and 2) "dying." Both events results in the cessation of information flow between two observers. In both cases one of the observers appears to "die"from a third person point of view, but stays alive from a first person point of view. In the first case the cessation of information flow is due to a relativistic effect. In the second case, the continuing of the information flow is due to a quantum effect. The following must be assumed: 1) that the black hole is large enough that the tidal forces do not rip apart the observer falling into it2) death occurs in one branch of the multiverse but not in another.There is definitely a relationship between entropy and black holes as Hawkings has shown and there is a relationship between entropy and information. This topic is ripe for a nice thought experiment.GeorgeStephen Paul King wrote: Dear Jean-Michel and Hal, All good humor aside, Hal makes a good point! The conditions that would exist as one approaches the event horizon seem to be such that any signal would be randomized such that the end result would be that Nature prevents infinite information (or conclusions requiring infinite computational power) from reaching any finite part of itself. Interestingly this seems to be the same situation as what forms an event horizon (around a space-time singularity) in the first place. Could it be that this is an active example of the so-called anthropic principle? It also reminds me of a solution to the Quantum Suicide problem! Kindest regards, Stephen SNIP
Infinite computing;self-organization
Here is a line of reasoning that is a frontal assault on extant (inadequate) AI paradigms conjoined with the question of 'self-organization' AND shining a light of awareness on -the important- Turing/computation question that .. comes AFTER .. the Halting Problem: Self-organization .. which themata includes inside-to-out emergent productivity .. AND COVALENTLY .. sensitive adaptability to/with any/all external effective information and energy .. is one on one isomorphic with the one important behavior that comes after any resolution of a 'halting problem' - and therefore supercedes it: Can a (computational) system which 'halts' [for any reason whatsoever] .. restart or re-initiate itself? Even if to deal with or process an entirely different question or computation. There is no self-organization if there is an absense of capacity to function sans external inputs. The Halting Problem is a minor issue compared with ReActivation Capacity?. But interestingly, because the question of ReActivation Capacity subsumes a greater scope of event space (information) than any given instantiation of the Halting Problem, there are more informational resources that can be brought to bear on 'the question', so essentially, the ReActivation Capacity issue is easier to answer - in the general, if not in the particular. Another way of juxtaposing the above questions is to bring in the relationship: relevance (opportunistic pertinence). If a computation would take longer than the age of the universe .. why would it/anyone bother instantiating the computation? It wouldn't just be a waste of energy, it would be an abuse of it. And any self-relevant system worth its own respect wouldn't engage in the effort. Self-organization - as a global themata - has to include additionally any and all co-habitation of any possible emergents coming out of self-organizing events (at and among any and all tiers of activities). And such products must be prior, current and forward, relatable .. in order for 'self-organization' to be a wholly self-consistent phenomenon. Therefore, Halting may or may not occur in given local event spaces, but, Activation/ReActivation -will- occur as long as relation and relational relevance is an a priori priority to 'existence'. Jamie Rose Ceptual Institute Feb 10, 2003
Re: Infinite computing: A paper
There are other possibilities to obtain hypercomputers or Infinite Time Turing Machines: For instance, from general relativity: put a computer in orbit around a black hole, start an infinite computation on it, arrange that the results are sent to you by radio, and jump into the black hole: when you reach the horizon, you get the result of the infinite computation (and witness the end of the rest of the universe). For a survey: arxiv.org/pdf/math.LO/0209332
Re: Infinite computing: A paper
Jean-Michel Veuillen writes: There are other possibilities to obtain hypercomputers or Infinite Time Turing Machines: For instance, from general relativity: put a computer in orbit around a black hole, start an infinite computation on it, arrange that the results are sent to you by radio, and jump into the black hole: when you reach the horizon, you get the result of the infinite computation (and witness the end of the rest of the universe). For a survey: arxiv.org/pdf/math.LO/0209332 ...and burn to death as infinite amounts of radiation fall on you in a finite time? Maybe the universe is like a character from a spy novel: it could tell us what it knows (solving the halting problem, etc.), but then it has to kill us. Hal F.
Re: Infinite computing
Dear Jean-Michel and Hal, All good humor aside, Hal makes a good point! The conditions that would exist as one approaches the event horizon seem to be such that any signal would be randomized such that the end result would be that Nature prevents infinite information (or conclusions requiring infinite computational power) from reaching any finite part of itself. Interestingly this seems to be the same situation as what forms an event horizon (around a space-time singularity) in the first place. Could it be that this is an active example of the so-called anthropic principle? It also reminds me of a solution to the Quantum Suicide problem! Kindest regards, Stephen - Original Message - From: Hal Finney [EMAIL PROTECTED] To: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Monday, February 10, 2003 12:19 PM Subject: Re: Infinite computing: A paper Jean-Michel Veuillen writes: There are other possibilities to obtain hypercomputers or Infinite Time Turing Machines: For instance, from general relativity: put a computer in orbit around a black hole, start an infinite computation on it, arrange that the results are sent to you by radio, and jump into the black hole: when you reach the horizon, you get the result of the infinite computation (and witness the end of the rest of the universe). For a survey: arxiv.org/pdf/math.LO/0209332 ...and burn to death as infinite amounts of radiation fall on you in a finite time? Maybe the universe is like a character from a spy novel: it could tell us what it knows (solving the halting problem, etc.), but then it has to kill us. Hal F.
Re: Infinite computing
Stephen, Amazingly, I had kind-of the same thought. From the point of view of information flow, there seems to be an analogy between 1) falling down into a black hole and 2) "dying." Both events results in the cessation of information flow between two observers. In both cases one of the observers appears to "die"from a third person point of view, but stays alive from a first person point of view. In the first case the cessation of information flow is due to a relativistic effect. In the second case, the continuing of the information flow is due to a quantum effect. The following must be assumed: 1) that the black hole is large enough that the tidal forces do not rip apart the observer falling into it 2) death occurs in one branch of the multiverse but not in another. There is definitely a relationship between entropy and black holes as Hawkings has shown and there is a relationship between entropy and information. This topic is ripe for a nice thought experiment. George Stephen Paul King wrote: Dear Jean-Michel and Hal, All good humor aside, Hal makes a good point! The conditions that would exist as one approaches the event horizon seem to be such that any signal would be randomized such that the end result would be that Nature prevents infinite information (or conclusions requiring infinite computational power) from reaching any finite part of itself. Interestingly this seems to be the same situation as what forms an event horizon (around a space-time singularity) in the first place. Could it be that this is an active example of the so-called anthropic principle? It also reminds me of a solution to the Quantum Suicide problem! Kindest regards, Stephen - Original Message - From: "Hal Finney" [EMAIL PROTECTED] To: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Monday, February 10, 2003 12:19 PM Subject: Re: Infinite computing: A paper Jean-Michel Veuillen writes: There are other possibilities to obtain hypercomputers or Infinite Time Turing Machines: For instance, from general relativity: put a computer in orbit around a black hole, start an infinite computation on it, arrange that the results are sent to you by radio, and jump into the black hole: when you reach the horizon, you get the result of the infinite computation (and witness the end of the rest of the universe). For a survey: arxiv.org/pdf/math.LO/0209332 ...and burn to death as infinite amounts of radiation fall on you in a finite time? Maybe the universe is like a character from a spy novel: it could tell us what it knows (solving the halting problem, etc.), but then it has to kill us. Hal F.
Infinite computing: A paper
Dear Bruno and Friends,
Let me point this paper as a possible counterexample to your argument:
http://xxx.lanl.gov/abs/quant-ph/0205093
Quantum Physics, abstract
quant-ph/0205093
From: Tien D. Kieu [EMAIL PROTECTED]
Date (v1): Thu, 16 May 2002 12:10:57 GMT (28kb)
Date (revised v2): Mon, 18 Nov 2002 04:26:38 GMT (38kb)
Quantum Principles and Mathematical Computability
Authors: Tien D Kieu
Comments: 9 pages in A4 size and 10pt fonts, 3 figures. Modified with a new
reference added for submission to QS2002
Taking the view that computation is after all physical, we argue that
physics, particularly quantum physics, could help extend the notion of
computability. Here, we list the important and unique features of quantum
mechanics and then outline a quantum mechanical algorithm for one of the
insoluble problems of mathematics, the Hilbert's tenth and equivalently the
Turing halting problem. The key element of this algorithm is the {\em
computability} and {\em measurability} of both the values of physical
observables and of the quantum-mechanical probability distributions for
these values.
Kindest regards,
Stephen
- Original Message -
From: Bruno Marchal [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Sent: Friday, February 07, 2003 2:58 AM
Subject: Re: Persons
Stephen Paul King wrote (in the FOR list):
The notion of intelligence that you mention below seems very close to
the notion of expressiveness that Peter Wegner develops in several of
his
papers. How do we balance the notion of the universality of computation
against this notion? It seems to me that the notion of universality
implies,
at least for Church-Turing machines, that they are all equally expressive
since, if we neglect the number of steps the machines take, any one
universal computer can perform exactly the same computation as any other.
It has been shown by Putnam that there is no perfect universal learning
machine, that is, machine capable to identify in a finite time any total
(everywhere defined on N) function.
If you allow a learning machine to change its mind infinitely often (that
is to change his explanation (program) when he get more big sample of the
function it tries to identify) AND if you allow a finite but unbounded
number of mistakes in the explanation, then, at least in principle, there
is a universal learning machine.
As a side note, I have read a paper discussing the computational
theory
of Malament-Hogarth machines in which it was pointed out that there does
not
exist a universality property for them. Would the notion, of
intelligence,
that you seem to imply below be more applicable to such rather than
machines
defined by the Church-Turing thesis?
I don't think so. Malament-Hogart Machines are abstract *computer* having
some infinite capacities (if I remember correctly). Learning machine are
just any computer programmed to generate explanation (in the form of
computer program) when they are given data (sequence of input/output).
Of course such machine are stream-interactive in a Peter Wegner related
sense.
Have you considered more abstract notions of computation that are not
limited to those expressible by physical systems? For example, could
there
exist a notion of computation that would involve functions C - C, where
C
is the space of complex numbers, analogous to the notion of
Church-Turing
computations as functions N - N?
Blum Shub and Smale have generalize the notion of computer by
computer on a ring (like R or C). They have prove in this setting
that the Mandelbrot set is undecidable (answering a conjecture by myself
and Penrose). From this you can look at the Mandelbrot set as a sort of
compactified projection of a universal dovetailer.
Blum Al. approach to computability gives interesting bridge between
numerical analysis and classical computability. I remember also having
read
a Los Alamos quant-phys suggesting to found quantum computing on
a similar ring-generalization. All those approach subsumes the (classical)
Church Thesis.
Bruno
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Re: Infinite computing: A paper
Stephen Paul King refers to:
http://xxx.lanl.gov/abs/quant-ph/0205093
Quantum Physics, abstract
quant-ph/0205093
From: Tien D. Kieu [EMAIL PROTECTED]
Date (v1): Thu, 16 May 2002 12:10:57 GMT (28kb)
Date (revised v2): Mon, 18 Nov 2002 04:26:38 GMT (38kb)
Quantum Principles and Mathematical Computability
Authors: Tien D Kieu
Comments: 9 pages in A4 size and 10pt fonts, 3 figures. Modified with a new
reference added for submission to QS2002
Taking the view that computation is after all physical, we argue that
physics, particularly quantum physics, could help extend the notion of
computability. Here, we list the important and unique features of quantum
mechanics and then outline a quantum mechanical algorithm for one of the
insoluble problems of mathematics, the Hilbert's tenth and equivalently the
Turing halting problem. The key element of this algorithm is the {\em
computability} and {\em measurability} of both the values of physical
observables and of the quantum-mechanical probability distributions for
these values.
This appears to be a variant on the Calude algorithm which got quite a
bit of publicity last summer. Like Calude, Kieu uses infinite dimensional
superpositions. I wrote on the everything-list on July 2,
: There was an article recently in New Scientist about a new way to geet
: computing beyond the Turing barrier. I think it is somewhat similar
: in spirit to the analog machines, in that it uses infinities, but it is
: based on the quantum computing model. The NS article is reprinted at
: http://www.cs.auckland.ac.nz/~cristian/smashandgrab.htm and the original
: paper is available at
: http://www.arxiv.org/abs/quant-ph/0112087.
:
: From the NS article:
:
:His suggestion is to think bigger: why not create a superposition
:of every conceivable state at once? Something like a hydrogen atom
:has infinitely many possible energy levels. While the levels start
:out well-spaced, they get closer as the energies grow higher, until
:they become almost indistinguishable. In a paper to be published
:in the inaugural edition of MIT's new journal Quantum Information
:Processing, Calude and Pavlov have shown that a superposition of an
:infinite number of energy states would allow a quantum computer to
:do things no classical computer can ever manage-almost like running
:forever in a finite time.
:
:This leap means that a quantum computer can overcome Turing's most
:famous barrier to computing power: the halting problem.
:
:...
:
:Calude is extremely proud of this result: he believes it could be
:implemented on a real-life quantum computer, laying much that is
:unknowable open to attack. Using infinite superpositions is rather
:theoretical, but not necessarily non-practical or non-testable,
:he says.
:
: My opinion is that infinite superpositions will never be practical hence
: his machine is of only theoretical interest.
I still don't see how one could hope to realize these ideas which depend
on infinite dimensional Hilbert spaces. Without claiming to have
investigated these machines too closely, it seems that establishing
the necessary superpositions would take an infinite amount of work,
and creating the infinite dimensional superposition would require an
infinitely large machine.
Hal F.
Re: Infinite computing: A paper
On 10-Feb-03, Stephen Paul King wrote:
Dear Bruno and Friends,
Let me point this paper as a possible counterexample to your
argument:
http://xxx.lanl.gov/abs/quant-ph/0205093
Quantum Physics, abstract
quant-ph/0205093
From: Tien D. Kieu [EMAIL PROTECTED]
Date (v1): Thu, 16 May 2002 12:10:57 GMT (28kb)
Date (revised v2): Mon, 18 Nov 2002 04:26:38 GMT (38kb)
Quantum Principles and Mathematical Computability Authors: Tien D
Kieu
Comments: 9 pages in A4 size and 10pt fonts, 3 figures. Modified
with a new reference added for submission to QS2002
Taking the view that computation is after all physical, we argue
that physics, particularly quantum physics, could help extend the
notion of computability. Here, we list the important and unique
features of quantum mechanics and then outline a quantum mechanical
algorithm for one of the insoluble problems of mathematics, the
Hilbert's tenth and equivalently the Turing halting problem. The key
element of this algorithm is the {\em computability} and {\em
measurability} of both the values of physical observables and of the
quantum-mechanical probability distributions for these values.
Kindest regards,
Stephen
I don't believe this paper has the significance it's authors think.
It invokes unrealisable infinities in setting up the computation and
in precision of measurements.
Brent Meeker
