Limits of computation

https://en.wikipedia.org/wiki/Limits_of_computation

by diziet • 9 years ago

121 18 9 years ago

en.wikipedia.org

pmontra• 9 years ago

About reversible computation and the Landauer limit: http://www.nipslab.org/node/5097

agumonkey• 9 years ago

I found out about Landauer principe last week and am fascinated about the mental shift.

vilhelm_s• 9 years ago

I think the key paragraph from the paper is this:

We would like to emphasize that the output of our logic gate can be fed directly as an input to a second similar device (as shown below) and so on, to perform all the calculations desired. Clearly, our logic gate is a combinational device; thus, the removal of the inputs makes the system revert to the initial state S0 (regardless of whether the final state was S0 or S1). If we want to remember the final state, we need to couple this device to a sequential device where a Landauer reset might be required and a minimum dissipation of kBT log 2 is needed.

In other words, the Laundauer limit applies to state machines, but not to combinatorial logic blocks. I guess in retrospect this should not be surprising: the derivation of the principle considers a computing machine which is in thermal equilibrium with its environment, so implicitly we model the machine as having some memory unit which has time to thermalize after each operation.

smeyer• 9 years ago

Landauer's principle defines a lower theoretical limit for energy consumption: kT ln 2 joules consumed per irreversible state change, where k is the Boltzmann constant and T is the operating temperature of the computer.[2] Reversible computing is not subject to this lower bound. T cannot, even in theory, be made lower than 3 kelvins, the approximate temperature of the cosmic microwave background radiation, without spending more energy on cooling than is saved in computation.

Well, technically, you just have to wait as the universe continues expanding if you want the temperature of the CMB to drop.

jakeogh• 9 years ago

Black Hole Farming: https://www.youtube.com/watch?v=Qam5BkXIEhQ

prashnts• 9 years ago

A cold degenerate star could conceivably be used as a giant data storage device, [...] purposes.

The cited link to this [1] is a fascinating email thread/essay which they call "Femtotech". I don't even understand most of the stuff, but it seems we're far, far from it.

[1] https://web.archive.org/web/20041025030505/http://www.cs.usu...

projectorlochsa• 9 years ago

I remember watching some documentaries and reading some articles, and remember Hugo de Garis talking about femtotech. I thought he was a pioneer in the technology, seems he's just a bystander.

He and Ben Goertzel seem to look as pioneers but never produce something tangible.

rorosaurus2• 9 years ago

Fascinating analysis! The section "Building devices that approach physical limits" reminds me of a rock Kurzweil mentions in "The Singularity is Near" [1]. Although it's not as a cosmic scale, it's a similarly interesting exploration of the limits of computation!

“How Smart Is a Rock? To appreciate the feasibility of computing with no energy and no heat, consider the computation that takes place in an ordinary rock. Although it may appear that nothing much is going on inside a rock, the approximately 1025 (ten trillion trillion) atoms in a kilogram of matter are actually extremely active. Despite the apparent solidity of the object, the atoms are all in motion, sharing electrons back and forth, changing particle spins, and generating rapidly moving electromagnetic fields. All of this activity represents computation, even if not very meaningfully organized. We’ve already shown that atoms can store information at a density of greater than one bit per atom, such as in computing systems built from nuclear magnetic-resonance devices. University of Oklahoma researchers stored 1,024 bits in the magnetic interactions of the protons of a single molecule containing nineteen hydrogen atoms.51 Thus, the state of the rock at any one moment represents at least 1027 bits of memory.”

[1] https://www.goodreads.com/quotes/1284270-how-smart-is-a-rock...

philipkglass2• 9 years ago

That seems to deeply confuse "a thing that can be modeled by computer" with "a computer." It's trying to commensurate the incommensurable. How much more efficient is a rock than your phone when it comes to computing the sum of two 64 bit integers? How much more efficient when it comes to storing and retrieving a megabit of JPEG data? I'd accept answers in the form of joules per operation.

The very questions are faulty. A factory-stock rock is not a programable logic or memory device. If it computes at all, it only computes being-a-rock.

This rock analogy is the sort of sloppy thinking that takes someone from "it takes at least 38 petaflops to simulate a conscious human brain" (currently unknown, but not obviously incorrect) to "the human brain is a petaflop-class supercomputer" (WTF, no, category error).

the8472• 9 years ago

It's basically saying that the universe is a special kind of computer that computes state transitions according to the rules of physics, presumably at the planck scale, which is far beyond what our simplified models of said rules can manage.

This view of he universe seems to be fairly important and taken seriously since black hole thermodynamics, gravity as entropic force and similar concepts are derived from it.

jawarner• 9 years ago

This interesting theoretical tangent raises a good question about the way we measure information.

A laptop only computes being-a-laptop. What makes it useful is that we have assigned meaning to the physical output. That is, there is a homomorphism mapping the atoms on a computer to a logical program.

So any physical system is only computationally useful to the extent that we can define homomorphisms from its physical state to a logical system of interest.

The OP is about the physical limitations of the information stored in the underlying system as measured by entropy. I wonder if entropy is the operating definition here because it implicitly defines what logical system we use to identify the physical system.

kangxitenant• 9 years ago

https://arxiv.org/abs/1301.4504 quantum computation complexity prevents hawking radiation from being decoded before the black hole evaporates!

dorgo2• 9 years ago

There are noncomputable functions. For example: https://en.wikipedia.org/wiki/Busy_beaver

csl2• 9 years ago

If anyone is interested, I attempted to plot the first few Busy Beaver iterations: https://github.com/cslarsen/busy-beaver

dorgo2• 9 years ago

Busy beaver machines are, by definition, non-halting machines

Is this an error? I thought busy beaver must halt?

Limits of computation

Related Stories