Calculating A Theoretical Boundary To Computation 583
TMB writes "Lawrence Krauss and Glenn Starkman, astrophysicists at Case Western Reserve University (and in LK's case, author of a number of books including Physics of Star Trek), just submitted this nice little paper to Phys. Rev. Letters. It claims that in an accelerating universe, the existence of a future event horizon puts a fundamental physical limit on the total amount of calculation that can be done, even in an infinite time. This limit is much smaller than the traditional Hawking-Beckenstein entropy. Among other things, this implies that and Moore's Law must have a finite lifetime, here calculated to be 600 years, and that consciousness must be finite."
Roger Penrose (Score:3, Informative)
Physics of star trek (Score:3, Informative)
It's not a referer link, don't worry...
Re:enough! (Score:3, Informative)
Law [m-w.com] 6 a : a statement of an order or relation of phenomena that so far as is known is invariable under the given conditions b : a general relation proved or assumed to hold between mathematical or logical expressions.
arXiv reaches it's computational limit! (Score:5, Informative)
Re:enough! (Score:5, Informative)
A Fire Upon The Deep by Vernor Vinge (Score:4, Informative)
Strongly suggest you read Vernor Vinge's A Fire Upon The Deep - he develops a very interesting view of expansion of the universe and consciousness.
If you've not heard of Vinge before that isn't a big surprise, but he did write True Names as well - the very foundation of the cyberpunk/hacker genre. This is also a good read if you can actually locate it.
Submitted, not accepted (Score:2, Informative)
Re:enough! (Score:5, Informative)
Re:Infinite Wisdom? (Score:3, Informative)
Re:Roger Penrose (Score:5, Informative)
So, no, it isn't really like Penrose's work.
This paper has not been published (Score:5, Informative)
Re:Roger Penrose - linky link? (Score:2, Informative)
Here's why:
Kurt Godel DID prove that mathematics is infinite. No matter how many rules and computations, OF ANY KIND, that you write down (or program into a computer) those rules can't be complete and consistent. Which means that there are true things about those rules (laws, whatever) which cannot be proven by applying only those rules. Or the rules are inconsistent, which is to say you can prove something both true and false, which is to say wrong.
As an example, look at the computer program for a chess in here:
http://doug-pc.itp.ucsb.edu/online/plectur
This link is actually most of the contents of the book, for those who don't have it.
On a more personal note, Flyboy, I believe your statement can be shown to be inconsistent (and thus worthless) because you imply that a person should be able to distinguish intuition from fact. That this is a basic error has been pointed out by: Plato, Descartes, Kant, Husserl, and others who are indisputably great thinkers of the first degree. I would put Penrose in with them, and I would put you in the great mass of people who hardly understand anything but somehow insist on displaying their ignorance anyway.
Re:Is computation discrete? (Score:1, Informative)
Other work on physical limits to computation (Score:2, Informative)
Re:Infinite Wisdom? (Score:3, Informative)
Re:And in other news... (Score:3, Informative)
What we have is a theory (GR) that says that conventional acceleration of a massive object to lightspeed requires infinite energy.
GR doesn't state that FTL communication via quantum entanglement (for instance) is impossible (though that effect is also yet to be demonstrated as an FTL effect). This effect was used to explain the "ansible" used in Orson Scott Card's books. FTL communication would completely invalidate the conclusions reached in this paper.
There are other potential ways to achieve FTL travel that don't implicitly violate GR, such as wormholes or other 'doorways' into spaces that connect places in our universe with [much] shorter distances than connect them here. This is also the basis for many of the "hyperspace" ideas in science fiction. Also yet to be demonstrated...
My main point though is that this paper may well turn out to be way off in the fairly short term (non-constant or non-existent cosmological constant). It's not that original, since similar work had already been done using older assumptions about the Universe. I'd have suggested the authors find a more useful role for all that cleverness and effort, especially since it seems there is absolutely no practical use for this study... ;-)
Re:Roger Penrose - linky link? (Score:5, Informative)
Ummm.... no. Godel proved that the axiomatic system of Russel's PM allows the construction statements which can neccessarily neither be proven true nor proven false. There are other axiomatic systems that can be complete and consistent; IIRC it was in fact Godel who proved that the first-order propositional calculus is complete and fully consistent. Godel's fork only attaches to systems that allow the construction of statements about statements; many propositional systems (like the first-order propositional calculus) do not.
Oy.... where to start? Kant's Critique of Pure Reason is nothing but 600 pages describing how people distinguish intuition from fact (though admittedly Kant was using "intuition" in a sense that we don't normally use it today). Descartes wrote his Meditations as an attempt to remove "intuition" (again, closer to Kant's sense of the word than ours, but still) from philosophy. Plato, of course, says nothing about the subject directly but narrates several dialectical processes about the subject.
Re:Infinite Wisdom? (Score:3, Informative)
C: "I beat you senseless!"
A->C is not the same as ~C->~A.
A->C would be "If you look at me funny, I will beat you senseless!" taken as literal truth.
~C->~A would be "I will not beat you senseless if you do not look at me funny", and is not at all the same.
No, ~C->~A is "If I am not beating you senseless, you didn't look at me funny." Your statement above is ~A->~C, which, as you noted, is not logically equivalent to A->C.
Daniel
Bruce Schneier wrote something similar to this (Score:2, Informative)
Thermodynamic Limitations
One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)
Given that k = 1.38x10^-16 erg/Kelvin, and that the ambient temperature of the universe is 3.2K, an ideal computer running at 3.2K would consume 4.4x10^-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.
Now, the annual energy output of our sun is about 1.21x10^41 ergs. This is enough to power about 2.7x10^56 single bit changes on our ideal computer; enough changes to put a 187-bit counter through all of its values. If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to 2^192. Of course it wouldn't have the energy left over to perform any useful calculations with this counter.
But that's just one star, and a measly one at that. A typical supernova releases something like 10^51 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of the energy could be channedel into a single orgy of computation, a 219-bit counter could be cycled through all of its states.
These numbers have nothing to do with the technology of the devices; they are the maxiumums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
And they say there's no poetry in computing...
Re:Roger Penrose (Score:3, Informative)
Basically it is believed that it is very unlikely that you can do quantum simulation on a classical computer.
Re:And in other news... (Score:3, Informative)
This was the old "Steady State" theory (Score:3, Informative)
Re:Roger Penrose - linky link? (Score:2, Informative)
It was indeed Gödel who proved that first-order logic is both sound and complete. The latter fact is Gödels *completeness theorem*. These theorems establish that a given expression is a first-order theorem if and only if it is true in all models. In other words, provability coincides with validity.
The incompleteness theorem also applies to first-order logic. Despite of what one might think, the completeness-theorem and the incompleteness-theorem are not negations of each other as you seem to say. They are in fact both true properties of first-order logic. The incompleteness-theorem states that you can't axiomize the set of the natural numbers with a recursive set of axioms (a potentially infinite set of axioms) - you can't create such a recursive set of axioms that has the property that an expression is provable from it if and only if the expression is a true property of the natural numbers.
The problem is, that for any recursive and consistent set of axioms that tries to be axioms of the natural numbers, there will be expressions that can neither be proved or disproved from them. From the *completeness* theorem we can conclude that this must mean that there exist multiple models that satisfies all the axioms in the set and that differ with respect to satisfiability of certain expressions (because if an expression was true in any model satisfying the axioms, the completeness theorem states that there would indeed be a proof from the axioms). So even though you can make attempts at axiomzation of the natural numbers that look very convincing (ie they look like any model satisfying them would have to agree on any stateable property) these attempts will either be inconsistent (ie any expression can be proven from them) or they will be incomplete (ie there will be true properties of the natural numbers not provable from them, because of the fact that there exists other models of the axioms in which those properties are not true). Contrary to what some authors state, inconsistency does NOT have to be apparent. Early axiomatic set theory is a good example: It took many years before someone (Russell) came up with an inconsistency even though every well-formed expression (including all contradictiions) did in fact have a proof all along. This inconsistency was fixed by weakening one of the axioms.
Re:Roger Penrose (Score:5, Informative)
So for all you
Re:Roger Penrose (Score:2, Informative)
You mean "it is very unlikely that you can do quantum simulation on a classical computer in polynomial time". Since I make my living doing quantum simulation on classical computers I'm pretty certain it can be done.
Re:Infinite Wisdom? (Score:1, Informative)