Catch up on stories from the past week (and beyond) at the Slashdot story archive


Forgot your password?
Science Technology

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

Calculating A Theoretical Boundary To Computation

Comments Filter:
  • Sweet (Score:5, Interesting)

    by DrLudicrous ( 607375 ) on Wednesday April 28, 2004 @09:06AM (#8995246) Homepage
    I was a physics undergrad at Case, and actually had Starkman as a professor for a mathematical physics course. I have chatted with Krauss a few times since graduation on science topics involving public education. These are good guys, glad to see them headlining slashdot this morning.
  • And in other news... (Score:5, Interesting)

    by Glock27 ( 446276 ) on Wednesday April 28, 2004 @09:11AM (#8995282)
    Skewe's number of angels can dance on the head of a pin...

    This article contains a very large number of assumptions, which may well prove not to be the case (constant cosmological constant, no FTL communication/travel, no access to other universes etc. etc.). Still, an interesting intellectual exercise I suppose... ;-)

  • by heironymouscoward ( 683461 ) <heironymouscoward AT yahoo DOT com> on Wednesday April 28, 2004 @09:18AM (#8995338) Journal
    Can you even define consciousness?

    Are we talking about the physical computational capacity of a headful of neurons, which is finite by definition unless you believe that the brain can somehow reach into unknown dimensions somewhat like early CPUs used bank shifting to increase their RAM range?

    Or are we talking about the sensation we have of being alive, a sensation that is arguably simply generated by our brains as a mechanism to ensure our survival. Yes, the vaunted consciousness that reacts a full 1/4 second after the fact when we do most common actions such as crossing the road, kicking a ball, picking up a cup, or typing comments to Slashdot?

    The definition of "consciousness" is seriously under debate and it's meaningless to discuss whether it's finite or infinite.

    Most likely, consciousness is a sense, like sight or sound. Would you frame the discussion of your sense of smell in terms of computational power? No, me neither.

  • Re:enough! (Score:3, Interesting)

    by Curunir_wolf ( 588405 ) * on Wednesday April 28, 2004 @09:18AM (#8995348) Homepage Journal
    Moore's law was never intended to be a scientific theory. It was just a useful observation. It has never had anything other than economic incentive to keep it going. Using it to discuss the calculational ability of the universe is idiotic.

    Exactly. Moore's law only works because it gave Intel (and these days, AMD, too) a goal for predictable release cycles. It has absolutely nothing to do with physics.

    The idea of "consciousness" really doesn't either. No credible physicist would get involved in this kind of pure philosopical theorizing without some evidence.

    Have they provided some theory that also tells us the mass of a given consciousness?

    Find another category. This does not belong in "science".

  • assumptions (Score:2, Interesting)

    by countzer0interrupt ( 628930 ) <countzer0interrupt@yahoo. c o m> on Wednesday April 28, 2004 @09:22AM (#8995375) Homepage
    "consciousness must be finite"
    ... this only works if consciousness is based on computation, surely? It's getting into the area of metaphysics, but so far there's nothing to suggest that consciousness is based within the brain, let alone is computational.
  • by zptdooda ( 28851 ) <.moc.liamg. .ta. .mjpnaed.> on Wednesday April 28, 2004 @09:27AM (#8995430) Journal
    Is quantum tunnelling across the event horizon of a light cone possible, in the same way that this evaporates black holes? Then excess energy can seep into the limited space.

    And what if a light cone included a quasar? Are the physics of this understood well enough for it to be included in the general case?
  • by Weaselmancer ( 533834 ) on Wednesday April 28, 2004 @09:32AM (#8995467)

    "...consciousness must be finite."

    This assumes that consciousness is based solely on computation. Not proven yet.

    And for that matter, even if consciousness is nothing more than computation, how can we put a limit on an activity in space-time when we don't even know how space-time functions, or even how many dimensions it has?


  • Re:Exception (Score:3, Interesting)

    by RLW ( 662014 ) on Wednesday April 28, 2004 @09:34AM (#8995482)
    We live in a finite universe. So, all things which require a physical framework are finite. It's just that there's a lot of stuff and therefore a *lot* of possible states. From the point of view of a very limited life span we can never even come close to witnessing an even small fraction of the number of states for the universe.

    In fact there are limitations to everything. Even to our ability to determinie limitations.
  • Re:assumptions (Score:3, Interesting)

    by phfpht ( 654492 ) on Wednesday April 28, 2004 @09:37AM (#8995509)
    but so far there's nothing to suggest that consciousness is based within the brain, let alone is computational. Sure there's evidence to suggest that consciousness is based within the brain. If the brain is damaged, consciousness can be removed or reduced (level of). That alone is a strong ling that consciousness is brain based. Enough brain damage and one can die or be reduced to a vegitable, metaphorically speaking. That seems to be a distinct reduction in consciousness. Smaller brains seem to have varying but usually lesser degrees of consciousness. Dogs have some level of conscousness, but it doesn't seem to be to same degree as, say, humans or even chimps. Defining consciousness itself is difficult, though. Is consciousness merely intelligence? Intellectual capacity? Awareness of surroundings? Memory? A combination of these? Something else? Something else is a slippery slope, though, as one can define consciousness as something which is intentionally unmeasurable or unknowable.
  • by AllUsernamesAreGone ( 688381 ) on Wednesday April 28, 2004 @09:38AM (#8995518)
    Most likely, consciousness is a sense, like sight or sound.

    Or, even more likely, an emergent byproduct of highly complex strange loops and pattern matching that, unlike any sense, does not have an explicit biological presence.
  • by Kris Warkentin ( 15136 ) on Wednesday April 28, 2004 @09:38AM (#8995519) Homepage
    If this paper is true and there is a limit on consciousness, wouldn't it make the existence of an omnipotent being an impossibility?
  • Re:Infinite Wisdom? (Score:4, Interesting)

    by PineHall ( 206441 ) on Wednesday April 28, 2004 @09:42AM (#8995556)
    Interesting! If true, it fits the Christian faith. In the Bible, it says that Jesus being in very nature God emptied himself and was made in human likeness. (Look at Phil. 2:6-7).
  • by drinkypoo ( 153816 ) <> on Wednesday April 28, 2004 @09:42AM (#8995557) Homepage Journal
    The GP was pointing out what those of a scientific bent already know - nothing is true, everything is permitted. We only know what we have seen. When we say something is impossible, what we mean is that it's impossible under any conditions we currently know how to bring about, or can repeatedly observe from natural phenomena.

    So yes, the assumptions (at least most of 'em) are pretty decent ones. As I said to a friend of mine once who was bitching about his CD player requiring gravity to operate, "yeah, and gravity is so unreliable, too."

    I'm not sure Einstein has proved anything. We still call it a theory, right? That doesn't mean it's just a guess, but the word "theory" is a tip of the hat to the fact that there's always something we don't know.

  • The Last Question (Score:5, Interesting)

    by eclectro ( 227083 ) on Wednesday April 28, 2004 @09:43AM (#8995568)
    There are some intersting ideas [] as to what the end of the universe could be.

    There's also another theory about that if a couple particles collide with enough energy they can create a more perfect vacuum that would essentially "take over" the current universe (I suppose like an implosion). Maybe somebody knows the link for this.

    I mention this as a backdrop for an interesting short story by Isaac Asimov called The Last Question []. This link is a summary and contains significant spoilers, you may want to read the story first [] I think that it is apropos, as it deals with a powerful computer called Multivac.

    This story is interesting to read, and interesting humanistic view. Good for pondering this slashdot thread/story. Good science fiction is useful.

  • by DrLudicrous ( 607375 ) on Wednesday April 28, 2004 @09:51AM (#8995623) Homepage
    I've always thought that life would probably require a heady number of different chemical elements, thus we would find it in areas of the universe with an abudance of heavy elements (like gold, lead, etc.). My guess would be that this solar system is probably a 2nd or 3rd generation system meeting those requirements- 7-10 billion years ago there probably was not nearly as many star systems with the abundance of transistion metals that we have here. And I think those are just as necessary for "complex" life as the basic carbon, oxygen, hydrogen, etc. are for life was we know it.
  • by Jeremy Singer ( 717636 ) on Wednesday April 28, 2004 @09:55AM (#8995665)
    The speed of light is a practical limit to lots of physical processes. There was a date "Norman O. Brown day" that was posited as the day that human growth expanded at the speed of light away from the earth. This was a physical limit that the volume of human growth could achieve. Most things we can do have a practical limit that is much less than that. I guess the primary value of such papers is to beseech us to talk with more precision and stop claiming that things we are in contact with are actually infinite. I often talk about things that are semi-infinite. What I mean when I say that is that the things I am talking about are larger than I can conceive. So if I complement you on your infinite wisdom, it just means I think that you are smarter than me. Don't let it go to your head. I really mean semi-infinite.
  • Re:enough! (Score:2, Interesting)

    by mdrn28 ( 770727 ) on Wednesday April 28, 2004 @10:05AM (#8995769)
    I must respectfully disagree with the idea that consciousness has "absolutely nothing" to do with science. Just because science does not have an comprehensive model for how consciousness works does not mean that there won't be one in the future that can be verified with observational evidence.

    I'll go out on a limb here and propose that physicists are only considered "credible" if they stay very close to the established theoretical framework.

  • To the Naysayers (Score:1, Interesting)

    by Anonymous Coward on Wednesday April 28, 2004 @10:11AM (#8995828)
    Several people have come down negatively on this paper for discussing consciousness, moore's law, or the limits of civilization. As a soon to be Phd graduate in AI I'd like to state the following.

    It is plainly obvious to me, and to anyone who really has a clue, that the naysayers really don't know what they are talking about. The people who have written this paper are obviously well-versed in their fields, much more so than those who would presume to look down upon them. Physics has always been a core science, and I find it VERY interesting that regardless of manifestation the advance of physical computation has a 600 year hard limit at the current rate. That is not a long time at all, even by human terms.

    Several functioning theories of consciousness actually exist, of which computation is one, and none will ever be proven to be correct. We have a theory of gravity, not a theorem of gravity. Theorems only exist in artificial logical systems, like math. In the real world, it is only ever theories, which are never proven, only supported by empirical tests. Claiming that theories of consciousness haven't been proven is similar to christians claiming god exists because it can't be proven that it dosen't exist. An apparent failure of both logical reasoning and our current educational system...

    As to the physics this paper was based on itself, that of course could possibly be shown to be incorrect. However by use of the cosmological constant, an empirical observed value, instead of trying to include newer theories that would explain similar effects, the paper rests on physics we are quite familiar with. Instead of speculating based upon as of yet untested string or more (possibly) complicated theories.

    Moore's Law was an simple observation of the rate of development of microprocessors. Anyone who has actually seen the paper knows this. Someone has been having too much fun in conspiracy camp when they start thinking it was a marketing ploy.

    And finally, a personal opinion on consciousness. As someone who has read many papers on the subject in philosophy, psychology, neuroscience, and AI. It is without a doubt in my mind an entirely emergent computational phenomenon at the newtonian scale. Not involving quantum mechanics, souls, gods, aliens, orbital mind control lasers or anything else beyond the physical mechanisms contained in your head.
  • by clambake ( 37702 ) on Wednesday April 28, 2004 @10:12AM (#8995835) Homepage
    Any analog variable has an INFINITE number of states. A wave could have a frequency of 1Hz, 1.1Hz, 1.00057Hz, 1.2399327772883786682676376627676367267Hz, etc. If "computation" is defined as "the act or process of evaluating with numerical or mathematical methods" then there is no physical limit to computation when using analog data storage...

    The googleplex, a number that CANNOT be represented digitally (not enough atoms in the universe) can be easily represented by a particularly intelligent shade of the color blue.
  • by Vaste ( 735713 ) on Wednesday April 28, 2004 @10:21AM (#8995937)

    True Names []

    This is also a good read if you can actually locate it.

    Difficult to locate? 5th hit in Google is not what I'd call difficult to locate. (That's how it was a month ago anyway.)

    Oh, and yes, it's a great book/short story (medium story?). If you're the least interested in AI, god, conciousness, MMORPG, programming, computers or any combination thereof this is a must read.

  • by feelyoda ( 622366 ) on Wednesday April 28, 2004 @10:27AM (#8996005) Homepage
    I'm getting the feeling that strange forces, "dark" energy, 13D branes of string theory, etc. all have something in common.

    They remind me of the epicycles astronomers observed so many years ago.

    Simply put, our knowledge case seems not to be expanding, but diversifying, with many theories, and few ways to prove them.

    Take a physicist from 1900; tell them about a meteor about to hit the earth. He'd say we're screwed. Take one today; she'd say "deflect it with a nuke".

    The point: the entropy death of the universe is a very very very very very long way away. To say we won't be able to do something about it is depressing, and hopefully wrong.

    I think Ray Kurzweil had this idea first. Consciousness may well be something in the universe which directly counters entropy. Evolution does seem to go against the grain.

    Actually, I suggest to everyone that you read at least the first few chapters of "Age of Spiritual Machines" where he describes the accelerating pace of salient events.
  • by Jagasian ( 129329 ) on Wednesday April 28, 2004 @10:34AM (#8996065)
    So does this imply that all physical computers are finite state machines? Even when connected to the internet, their total number of computational states are finite, though extremely large, and therefore Universal Turing Machines are only a mathematical construct.
  • by heironymouscoward ( 683461 ) <heironymouscoward AT yahoo DOT com> on Wednesday April 28, 2004 @10:36AM (#8996080) Journal
    "emergent byproduct of highly complex strange loops" just means you don't know.

    The brain is a (hugely complex) collection of mental tools. For instance some of the tools that are fairly unique to the human brain:

    - sense of self
    - language
    - short-term memory
    - long-term memory
    - social feedback
    - empathy
    - self of justice
    - sense of time
    - abstract sense of danger
    - sense of opportunity

    All these mental tools (and many more I can't even name) will eventually be mapped and understood.

    Consciousness is, I believe, simply a photoshopped reality that one part of our brain feeds to the "front-end" so that we can operate usefully in a complex world.

    For example: we decide to pick up a cup of coffee. The decision happens, the signals get sent to our arm, we pick up the cup, and we start drinking. With a significant delay, our "conscious mind" - i.e. the parts of the brain associated with waking thought and action - register the event. We believe our consciousness is acting in real time, but in fact we're just reacting to a series of events that is happening unconciously.

    There is an extreme school of thought that suggests that there is no active mind at all, that everything we do is reactive and that our consciousness is simply a PR department that spins this ongoing chaos into some kind of coherent "I'm in charge" scenario that allows us to operate.

    In such a scenario, the consciousness is computing nothing.
  • by forii ( 49445 ) on Wednesday April 28, 2004 @10:51AM (#8996257)
    I have always though moores law to be crap, I mean its just some marketing scan to force us to upgrade slowly...

    Think of it as "Moore's Observation" instead. It wasn't meant to be a "Law" or a "Theory".

    Minge for example predicts that computing something will become instant,

    Computing something instantly may be possible, but transmitting the information necessary for that computation won't be. And that fact is the basis for this paper. Even if you could instantly perform every computation on every piece of information available to you forever, eventually the expanding universe will remove that information from your grasp. That puts a limit on what you can theoretically accomplish.
  • by Jagasian ( 129329 ) on Wednesday April 28, 2004 @10:55AM (#8996312)
    Penrose probably doesn't even understand what Godel's Incompleteness Theorem means. Hell, the fact that most people credit Godel with proving the incompleteness of formal axiomatic mathematics is proof that most people don't know math. Skolem's paradox can be seen as the first incompleteness proof and it predates Godel's proof.

    Skolem's paradox basically boils down to the fact that within axiomatic set theory you can prove the existence of uncountable sets, but if a model exists for the theory then it is countable. Hence according to the axiomatic system, there exist uncountably many sets, but the system can really only manifest countably many sets. This is similar to how Godel showed that formal arithmetic cannot manifest proofs for every proposition the formal axiomatic system claims exist.

    While Skolem's paradox is held amongst by many mathematicians as the first incompleteness proof, in my opinion, this proves something much more significant... it proves that axiomatic set theory is semantically inconsistent.

    Set theory has been problematic from the start, and even after axiomatizing it in order to avoid simple inconsistency... set theory is still plagued with inconsistency of a different form: the formalisms don't hold any meaning - they are semantically inconsistent. What the formalisms say contradicts what the formalisms mean.

    The problem is that lots of people don't understand math, and even many of those that do understand it, love it so much that they are unwilling to give up the flawed parts.

    For me, mathemathics is constructive recursive mathematics :) No inconsistency here. No incompleteness here. All math is computable!
  • by hweimer ( 709734 ) on Wednesday April 28, 2004 @11:02AM (#8996390) Homepage
    They claim that every computation step requires at minimum energy of ln 2 k_B T (k_B is Boltzmann's constant, T is the temperature of the system). This is only true for irreversible operations such as setting or erasing a bit.

    But computation doesn't have to be irreversible. There are various proposals on how to build reversible computers that don't consume this minimum energy per operation. More information about reversible computing can be found in this introduction [].
  • Encryption limits? (Score:4, Interesting)

    by harlows_monkeys ( 106428 ) on Wednesday April 28, 2004 @11:07AM (#8996447) Homepage
    So, how many bits do I need for a symmetric cipher key in order to push a brute force search past the computational limit of the universe?
  • Re:Roger Penrose (Score:5, Interesting)

    by Yartrebo ( 690383 ) on Wednesday April 28, 2004 @11:28AM (#8996659)
    Here's Turing's counter-example to bust Penrose's theorem:

    If a machine (human in this case) can simulate a single Turing machine, and a Turing machine can simulate it, then it is exactly as capable (though perhaps not as quick) as any other Turing machine.

    The first part is easy to prove: Any student who has learned Automata Theory should be able to simulate a Turing machine in their head, though it will be VERY slow and tedious.

    The second is harder, but there is no reason to think that a simulation of every particle that makes up a human, plus a small environment (air, ground, food, water) around her/him will successfully simulate consciousness. The fact that today's computers are not strong enough doesn't invalidate humans being bound to a Turing machine's capabilities.

    Any Turing machine is computational, therefore if the applications of Turing's thesis to humans holds, humans, and every part of them, including consciousness, are computational.

    As far as Heisenburg's uncertainty theorem and quantum mechanics goes, it can be inserted into the simulator using rand().

    Godel's Incompleteness Theorem doesn't apply to Turing's Theorem. Godel is talking about that there exists inconsistencies in any sufficiently complex langage (ie., the statement "this statement is a lie."). It doesn't contradict Turing's Theorem, since to disprove Turing's Theorem, we'd need to find a Turing machine that is incapable of simulating another Turing machine. All Godel says is that there will be non-sensical or impossible states in any Turing machine, but the machine can still work. (the proof that they exist is that English syntax can be programmed into any Turing machine, and the "this statement is a lie." statement inputted into the machine).

    And as far a philosophy goes, so what if I'm limited to 2^2^40 states. I'll never get anywhere near experiencing all of them in the life of the universe, assuming I live that long. And in the same way that computers can execute computer games with fantasy themes, a computation human has nothing interfering with dreaming, pretending, or religion (though it might point out the silliness of latter).
  • by Idarubicin ( 579475 ) on Wednesday April 28, 2004 @11:43AM (#8996847) Journal
    Any analog variable has an INFINITE number of states.

    Er, no. At least, not within the known bounds of quantum mechanics. Your mileage may vary.

    What we perceive as a continuously variable analog world just happens to have a *lot* of very closely-spaced discrete states. Each time you add volume, matter, or energy to a system you increase the number of available states by a large, but still finite, amount.

    A wave could have a frequency of 1Hz, 1.1Hz, 1.00057Hz, 1.2399327772883786682676376627676367267Hz, etc. If "computation" is defined as "the act or process of evaluating with numerical or mathematical methods" then there is no physical limit to computation when using analog data storage...

    Here we run into quantum mechanics once again. To take the measurement of the frequency of a wave, for instance--how do you resolve a difference down at the one part in a quintillion level? Essentially you run afoul of uncertainty principles. To reduce the uncertainty in your measurement of frequency to a low enough level to resolve such small differences, you have to pay a price in measurement time. Actually, you have the same problem when you write your data in the first place. See also my remarks about number of accessible states--storing an analog wave with a finite precision will require a certain amount of matter and energy, neither of which is available in infinite amounts*.


  • by A55M0NKEY ( 554964 ) on Wednesday April 28, 2004 @12:36PM (#8997436) Homepage Journal
    I wouldn't be suprised if someone could be consious while missing the right half of the brain or consious while missing the left half of their brain, but I would be very suprised if someone were consious while missing their entire brain.

    All you have said is that each half of the brain is capable of consiousness independently. When both halves of the brain are present in a skull, then they act together via interconnections to produce a single consiousness.

    You could say that complete brains consist of the right half, the left half, and the interconnections between them, without the interconnections ( an intact corpus callosum ) you indeed have 2 independently functioning halves that could possibly each be independently consious.

    Imagine being the 'other half' of yourself if you had your corpus callousum cut, eternally watching the other half of your brain control things until one day, you gain control of the left hand, pick up a knife and stab yourself while the shocked right hand tries to block your fatal blow.

  • by Anonymous Coward on Wednesday April 28, 2004 @01:37PM (#8998186)
    Yes you smarty pants .. if you do adiabatic process, you can always remain in equilibrium. Reversible computing requires storing all intermediate results. Have you ever figured out how much space it will take. Yes go and soak your head. MIT was touting about this for long time, never worked.
  • Re:Infinite Wisdom? (Score:3, Interesting)

    by pclminion ( 145572 ) on Wednesday April 28, 2004 @03:07PM (#8999443)
    Christians are promised an enternal life in Heaven. We are not promised omniscience or omnipotence.

    How can eternal life be consistent with the second law of thermodynamics? All things tend toward disorder -- to create order requires energy, and an increase in entropy which outmatches the decrease in some localized area. Hence God must have an infinite supply of energy in order to give you eternal life. Where does this energy come from?

  • by What is a number ( 652374 ) on Thursday April 29, 2004 @12:09AM (#9004196)
    If you take a persons brain and disconnect the two halves, there is, in some sense, 2 consciousnesses (sp!). THIS HAS BEEN DONE:

    With one child whose brain was split - consistently one half wanted to grow up to be a cowboy, the other an astronaut.

    Sorry I don't have a link - google is the obvious answer here.

    The interesting thing about the case was that it is hard to communicate with each half separately - especially when one half tends to be in change of communication, the other something else, etc. But there are ways to do it.

    Actually, coincidentally, I think I first read about this in Penrose's book...

    I type this every time.

Money can't buy love, but it improves your bargaining position. -- Christopher Marlowe