Calculating A Theoretical Boundary To Computation

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."

Comments

The Last Question

[eclectro]

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.

Not True with Reversible Computing

[hweimer]

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.

Re:Roger Penrose

[Yartrebo]

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