Please create an account to participate in the Slashdot moderation system

typodupeerror

## Calculating A Theoretical Boundary To Computation583

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."
This discussion has been archived. No new comments can be posted.

## Calculating A Theoretical Boundary To Computation

• #### Roger Penrose (Score:3, Informative)

on Wednesday April 28, 2004 @08:03AM (#8995221)
This doesn't mention Penrose's work, which is very much like this.
• #### Physics of star trek (Score:3, Informative)

on Wednesday April 28, 2004 @08:08AM (#8995258)
Physics of star trek [amazon.com]

It's not a referer link, don't worry...

• #### Re:enough! (Score:3, Informative)

on Wednesday April 28, 2004 @08:11AM (#8995283) Homepage
Exactly - Moore's law is certainly not a real scientific law. It often approximates what actually happens, but because it's based on human activity, it's not very precise. Humans are unpredictable, and thus, cannot possibly be the basis for a scientific law (as far as I know)

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)

on Wednesday April 28, 2004 @08:15AM (#8995315) Homepage
Please use the mirrors. In Australia, the closest one is here [arxiv.org].
• #### Re:enough! (Score:5, Informative)

on Wednesday April 28, 2004 @08:23AM (#8995391)
Ummm...read that again. Moore's Law is not the basis of this paper. Physicists and mathematicians using economic theories (yes, Moore's Law is economic in nature) to predict physical laws are neither published nor credentialed. The finiteness of Moore's Law is an implication of the findings of this paper.
• #### A Fire Upon The Deep by Vernor Vinge (Score:4, Informative)

on Wednesday April 28, 2004 @08:24AM (#8995398) Journal

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)

on Wednesday April 28, 2004 @08:25AM (#8995416) Homepage
• #### Re:enough! (Score:5, Informative)

on Wednesday April 28, 2004 @08:29AM (#8995447)
Have you read the article? All it states is that no civilisation could possibly extend Moore's Law beyond 600 years. That's the only reference to Moore's Law in the entire article, and its a reasonable one. It puts into terms we can (just about) understand the implications of the discovery. Who knows what 1.5 * 10^220 bits of information processed is? But 600 years of development at the current rate is slightly more imaginable (although, I'll admit, only marginally so).
• #### Re:Infinite Wisdom? (Score:3, Informative)

on Wednesday April 28, 2004 @08:33AM (#8995476)
Very interesting. In some Islamic phylosophies, God is an infinite being who is not inside or part of the universe (he has no physical attributes) and hence not limited by any means, who has not been born, is unique and does not produce any child or such. His prophets, on the other hand, all are normal human beings with all of the limitations.
• #### Re:Roger Penrose (Score:5, Informative)

on Wednesday April 28, 2004 @08:39AM (#8995526)
I haven't seen anything by Penrose which is like this. In fact, this article states an assumption ("consciousness is fundamentally computational in nature") that directly contradicts Penrose's most well known result, a rather dubious pseudo-mathematical "proof" that consciousness _cannot_ be computational as a consequence of Godel's Incompleteness Theorem.

So, no, it isn't really like Penrose's work.
• #### This paper has not been published (Score:5, Informative)

on Wednesday April 28, 2004 @09:07AM (#8995784) Homepage
Not commenting on the paper itself, but it has been submitted to PRL, not accepted. It hasn't gone through that wonderful process of peer-review that is the very heart of the scientific method (that and falsifiability but thats another topic). NASA has been setting a particularily bad example here with science by "press release". PRL is not an easy journal to publish in, lets wait until other experts have a look and not cheat the scientific method like this. PRL should not be mentioned in connection with this paper until this get published - Anyone can submit a paper to PRL...

by Anonymous Coward on Wednesday April 28, 2004 @09:28AM (#8996009)
I feel exactly the opposite, that "The Emperor's New Mind" is the greatest work of philosophy written in the last 20 years.

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/plecture /penros e/

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)

by Anonymous Coward on Wednesday April 28, 2004 @09:44AM (#8996169)
Actually one consequence of Quantum Mechanics is that an analog variable CANNOT have an infinite number of states. There are, for instance, a finite number of shades of the color blue. Any shade has a wavelength, which can be measured to a precision limited by the Planck length. I don't have the motivation to do all the math, but I think this gives us about as many possible shades of blue as there are atoms in the Milky Way. Certainly a huge number, but very definitely finite.
• #### Other work on physical limits to computation (Score:2, Informative)

on Wednesday April 28, 2004 @09:55AM (#8996306)
I strongly suggest that anyone who is into this sort of work check out Seth Lloyd's Ultimate Physical Limits to Computation [arxiv.org]. It's quite interesting. I saw him speak a few years ago. People had told me that we would "always find a way" to increase computation, which seemed like utter silliness to me. I'm glad to see that some folks are a little more sensible about this.
• #### Re:Infinite Wisdom? (Score:3, Informative)

on Wednesday April 28, 2004 @10:07AM (#8996446)
Christians are promised an enternal life in Heaven. We are not promised omniscience or omnipotence.
• #### Re:And in other news... (Score:3, Informative)

on Wednesday April 28, 2004 @10:28AM (#8996668)
Considering that we have Einstein with a proof that faster than light is impossible,

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... ;-)

on Wednesday April 28, 2004 @10:28AM (#8996669) Journal
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.

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.

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

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)

<dburrows@d[ ]an.org ['ebi' in gap]> on Wednesday April 28, 2004 @11:00AM (#8997048)
A: "You look at me funny..."
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)

on Wednesday April 28, 2004 @11:02AM (#8997065)
in Applied Cryptography:

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)

on Wednesday April 28, 2004 @11:06AM (#8997115) Journal
Except it is currently unknown whether quantum mechanical systems can be simulated with even probabilistic Turing machines. In fact, if it is possible to do so in polynomial time, you can do anything a quantum computer can do in polynomial time and so you can factor numbers and solve the discrete log problem in polynomial time.

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)

on Wednesday April 28, 2004 @11:33AM (#8997405)
No. As you go from v=0 to v=c the energy required to accelerate goes to infinity. On the other side it's mirrored... as you slow down from v=infinity to v=c the energy required goes to infinity. But time is definitely reversed at all velocities greater than the speed of light :)
• #### This was the old "Steady State" theory (Score:3, Informative)

<rpresser@NospAm.gmail.com> on Wednesday April 28, 2004 @11:49AM (#8997575) Homepage
In the 20s, when expansion was first detected by Dr. Hubble [wikipedia.org], the "Steady State" theory [wikipedia.org] was advanced to explain it as an alternative to the "Big Bang" theory [wikipedia.org], which the late Sir Fred Hoyle [wikipedia.org] found offensive. (By the way, he coined both phrases - Big Bang and Steady State.)

by Anonymous Coward on Wednesday April 28, 2004 @12:22PM (#8998004)
You're right on some thing and wrong on others.

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)

on Wednesday April 28, 2004 @12:31PM (#8998110) Homepage
Penrose in recent years isn't saying "consciousness isn't a computer." Rather in collaboration with Stuart Hameroff [arizona.edu] and a number of physicists is saying that "consciousness is a quantum computer."

So for all you /.'ers whose first reaction is: "He says we're not computers. Uncool!" consider the contrary reaction: "He says we're quantum computers. Way cool!" Also note that, as all /.'ers should know, quantum computers don't have the same limitations as conventional computers on capacity, thus the well-known threat they pose to encryption, being able to break it (in theory) in trivially short time periods.
• #### Re:Roger Penrose (Score:2, Informative)

on Wednesday April 28, 2004 @12:43PM (#8998281) Homepage

Basically it is believed that it is very unlikely that you can do quantum simulation on a classical computer.
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)

by Anonymous Coward on Wednesday April 28, 2004 @01:49PM (#8999205)
Islam, Judaism, and Christianity pretty much share most of the beliefs in the Old Testament...

The star of riches is shining upon you.

Working...