LWN: Comments on "The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation"

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

muwlgr — 2008-08-12T09:32:22+00:00

A pair of nanotech/reverscomp articles that amazed me some years ago :
http://www.cise.ufl.edu/research/revcomp/physlim/PhysLim-...
http://www.zyvex.com/nanotech/mechano.html (like, Babbage engine 
returns!:>)

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

aigarius — 2008-07-13T16:13:23+00:00

I like the narrative style of the (CreativeCommons licensed) Accelerando more.
http://www.accelerando.org/book/

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

mcortese — 2008-07-03T18:03:51+00:00

So what? It only proves the limits of a 1-kg block of matter, assuming that it will be a reasonable piece of hardware for a laptop.

But by the time we reach the storage limit (to take one), we may have a different concept of what a "laptop" is. For example it could be the union of a 1-kg device with no storage at all, linked to a physically large storage located somewhere far away, with a terabitpersecond wireless connection.

What Dr. Lloyd calls his "Ultimate Laptop", is indeed bound to the current understanding of what a laptop is, which reduces his work back to a mere discussion of the applicability of Moore's Law to a particular manufacturing assumption.

Whether you believe or not that humankind will always find ways to perpetuate Moore's Law through a shift to new techniques, for sure it won't be this paper to give you any proof.

Factoring in I/O

jd — 2008-07-01T23:08:31+00:00

I/O is a relatively simple thing to factor in, provided we assume something analogous to the
Transputer, which communicated to "adjacent" nodes, where "adjacent" would either mean the
physically adjacent Transputers or the ones that would be logically adjacent if you used a
hypercube topology. The latter was generally faster, but here we don't have wires and can't
organize the atoms that way.

Basically, you need to consider a cluster of atoms, such that the cluster supports your
logical operation plus the ability to receive input and the ability to deliver output. The
Transputer used four serial connectors. Could we have more than that, here? Well, that depends
on the maximum density you could pack the atoms and the arrangement they took. The tetrahedron
is a nice, packed structure, and if I remember correctly, gives you 6 bonds per atom. (One
bond to the other three atoms in the tetrahedron, plus one bond to each of the three adjacent
tetrahedrons.) Each bond is capable of conveying data, so each bond can be regarded as a
connector. As with the Transputer, data can flow in either direction but can only flow in one
direction at a given time.

So, your processing atom has 6 lines for I/O. Assuming it can only handle two input lines and
one output line (a very basic gate), you have sufficient lines to process at double the I/O
bandwidth if necessary without running out of data. Assuming an I/O transaction to be simply
the delivery of information to a processing atom used for I/O, a gate operation, and then the
delivery of the result, each I/O operation consumes the time for a gate transaction plus twice
the time it takes for an electron to travel the distance between atoms in this structure.

(Not sending to a specific atom is equal to ANDing with zero, so this drives the heat output
up considerably. We are assuming gate transactions are based on instantaneous input values and
do not need to be actually measured, per se. Otherwise, we need to add in the time for two
independent states to stabilize and be measured, where the two state changes do not take place
simultaneously from the perspective of the observing atom. IIRC, the correct value to use is
1.5x the time it takes to stabilize for a single state.)

So, the total time for a local transaction is now the time for three gate transactions, plus
the time for four electron hops, plus optionally 3x the time it takes for a state to
stabilize. An electron hop is limited by the speed of light, but the exact distance depends on
the forces involved. For simplicity, I will disregard it, but if you want a more accurate
value, I suggest picking the carbon atom and maybe diamond as the structure, then figure out
the correct values from that. The other values are in the article.

However, transactions are multicast. Each I/O atom can deliver to anywhere between zero and
two target processing atoms (assuming it cannot deliver to the originating atom), plus zero to
three other I/O atoms, which can in turn cascade the data to processing atoms and other I/O
atoms. The exact number depends on what happens to be adjacent.

This means a signal can go between any given processing atom and any given set of processing
atoms (excluding any set including itself). We use the per-hop calculation to calculate the
average time for an actual transaction by calculating the average volume you would need to
transmit over. The maximum time is the time for a signal to sweep the entire structure. The
maximum time assuming any-to-any communication will be for the signal to sweep half the
distance.

Because 2/3 of the atoms are used for I/O, and because it takes quite some time for data to
reach a given processing atom, the maximum theoretical speed should be reduced accordingly.

This has assumed we are using electrons to convey data, but we don't have to. An electron, at
suitable speed, striking a nucleus, will release an X-Ray. An X-Ray, at suitable energy,
striking a nucleus, will release an electron. This is known as X-Ray fluorescence and is a
widely-used technique.

This reduces (but does not eliminate) the need to use processing atoms as I/O switches. If
there's line-of-sight, it's possible for an X-Ray to deliver data to a target cluster of
atoms. You would use the cluster to absorb the X-Rays and then deliver the data as electrons
to the processing atom. The processing atom would need to (somehow) fire an electron fast
enough to convert the result back into an X-Ray.

This I/O is point-to-point, not multicast, but has significantly less latency, allowing for
far larger "neighbourhoods".

Hmm... H-bar? What's the problem with it?

SEMW — 2008-06-26T16:52:48+00:00

I'll second the motion. If anyone's interested, my favourite way of embeding Tex in web pages is jsmath, which has excellent browser support and uses the proper TeX fonts if you have them installed (images and unicode fonts if you don't). MathML is the other option, but very few browsers support it at the moment (I think Opera 9.5 is the only one to fully support it out-of-the-box, though Firefox is on its way).

Storage increase in laptops:

ekj — 2008-06-26T13:44:21+00:00

That's true. You get a 7oom quicker computer for $5000 now, compared to a similar sum of money
(inflation discounted) 25 years ago.

But people don't BUY those. They buy $500 - $1000 computers instead, and spend some extra on
getting small rather than powerful at that. (laptop-hds are much more expensive pro GB than
desktop-hds)

It's already all in the IO. I've got one 17" laptop and one 12", the difference isn't in the
power (it's there, but I rarely care) but in the fact that the 17" is just better if I need a
lot of screen pixels or a lot of physical screen-size.

Storage increase in laptops:

Duncan — 2008-06-26T11:36:49+00:00

However, there's another dimension that you've failed to figure in, that 
of overall computer size.  It turns out that at least for the past 25-50 
years (the 50 years earlier measured, or the 25 here) at least, we've 
found the practical benefits of overall computer miniaturization 
beneficial as well, such that in practice they've absorbed some of those 
OOMs you mention.  It's the oft pointed out main-frame (room size) > 
mini-computer (large appliance size) > desktop (medium appliance size) > 
laptop (small appliance size) > handheld/umpc > cell-phone > watch... 
trend.  As storage and computation increases, we've chosen to trade off an 
OOM every decade or so to graduate to the next smaller sized unit.

If the per-decade size generation trend continues, normal people won't be 
using laptops anymore in 25 or even, really, 10 years, as we'll downshift 
a size or two or three instead.  Just as trends indicate people are now 
switching to laptops instead of desktops and UMPCs instead of laptops, 
because the smaller size now has more power than the larger size did a few 
years previously and it's all the power really needed at that usage point, 
a decade from now, computers the size (and likely cost as well) of today's 
remotes/MP3-players/cell-phones will be the norm (low/high-end), while 
packing the computing power of today's dual-quad-core servers.

OTOH, we're up against the wall of the human body's I/O limitations 
already, probably the reason we didn't migrate smaller several years ago, 
when the computing power of a desktop first exceeded that really necessary 
for office applications and the like.  Some people just like a full sized 
keyboard and a nice sized display, and that human interface is *NOT* 
shrinking with Moore's law, unfortunately.

For decades, Science Fiction's answer has been change the interface, voice 
recognition and eye-glasses displays, with direct neural tap interfaces 
predicted beyond that, but the required AI and materials science hasn't 
really made that first leap practical as yet, tho it /is/ tantalizingly 
close... but we've thought that for over a decade, as well.

Still, the keyboard and large external display as human I/O method is 
simply going to have to give if we're to graduate down below the UMPC 
level.  Or maybe we'll end up with ubiquitous built-in 
keyboard/display/Internet units everywhere, and plugin/wireless-in our 
multi-terabyte-storage-multi-cored-USB-thumb-drive-sized "personal 
computer" everywhere we go, much as folks are doing with the thumb-drives 
themselves today?

Or, just perhaps, the just-a-few-years long trend of actually shrinking 
cost will become the dominant factor going forward, and those now $400 
UMPCs like the Eee and friends will be $30-50 or even <$10, while 
containing the power and storage of today's big-drive quad-core 
desktop/servers, but with the permanent data stored "in the cloud" and 
with I/O to ubiquitous permanent displays/keyboards where needed as 
mentioned above, so the individual units become disposable, like the 
digital watches one can now buy in the dollar store.

I really do think that the average person's usage really is being met now, 
thus the focus on smaller but more important CHEAPER we are seeing, and 
that that fact is not going to change -- UNLESS some "killer app" like 
truly practical general purpose (not limited purpose/vocab as we see now) 
voice recognition and hidef spectacles displays suddenly appear.  
If /that/ happens, then we'll see the drive to smaller (but with whatever 
resources are necessary to drive the voice recognition AI) reassert itself 
over cheaper, down to the point they can be embedded in the eye-glasses 
themselves.  Since such a practical general purpose voice recognition AI, 
should it appear, is likely to be fairly resource intensive for even 
today's multi-core desktops, the process of miniaturizing the hardware 
(and power requirements) to the watch-battery size point, for embedding in  
those spectacles, is going to take a fair bit of that 25 years, anyway.  
Beyond that... well, we'll just have to see where that 
neuromanceresqe "jacking in" tech is, at that point.

Duncan

Academic compression

forthy — 2008-06-26T08:27:35+00:00

But most of the mark details are useless, all you require is a single bit "pass" or "fail". Nobody is going to read your detailed marks for each semester exam later in your career. For all reasonable degrees, it's basically a two-bit information: Dropout, Bachelor, Master, PhD. Don't think "dropout" is a career limiter: The world's richest man is a dropout.

I'm quite sure I'll see several limits to the exponential growth in my lifetime (probably the next 50 years), at least I already experience one (probably temporal) limit: clock frequency didn't go up much the last 5 years. There however is a way to get more power out of computers: write better software. It is amazing what vintage computer fans get out of ancient designs. We are used to write software for computers that get faster and have more memory, so we write a lot of slow, bloated software.

Due to the fact that single-threaded CPUs don't get (significantly) faster anymore, we probably should start right now: Use better algorithms to make single-threaded programs faster.

1000 single bit operations per FLOP

mikov — 2008-06-25T00:06:55+00:00

Wow, thanks! I have nothing to say except to retract my idiotic suggestion of implementing the
adder with a truth table :-)

I have to agree with "nix" that this is very impressive. Your post deserves an article of its
own.

1000 single bit operations per FLOP

nix — 2008-06-24T22:49:20+00:00

That came off the top of your head?!

Allow me to briefly say 'wow', if so. :)

Storage increase in laptops:

ekj — 2008-06-24T07:29:05+00:00

The scary thing, or atleast the mindboggling one is trying to extrapolate this and imagine
what we'll be DOING with it.

Okay, so you say 6 OOM in 25 years. I think if you compare similarily-priced computers its
actually more than that. The TRS-80 cost a lot more (inflation-corrected) in 1983 than a 2GB
laptop cost today. I think the real number is more like 7OOM.

So, what does that mean if present trends continue for the NEXT 25 years ?

2GB * 10^7 ram.

It's a -gargantuan- number, it means your laptop by then will have more RAM than the
googlecluster has today. Infact it'll have RAM comparable to the sum total of ALL laptops in
USA today, give or take a OOM.

Academic compression

salimma — 2008-06-23T17:17:41+00:00

Yes; from 4 bits to 3 bits; a saving of 25% !

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

ekj — 2008-06-23T08:47:14+00:00

We're closer than this to universal limits on computation, if it's not reversible computing.

With non-reversible computing, flipping a single bit, as you say, costs energy. There's a
minimum energy it MUST cost, dependant on operating-temperature.

So, how much can a laptop do if it's only allowed to consume 10W, operate non-reversibly, and
operate at room-temperature ? I did the math for rec.arts.sf.science some time back, and may
very well have done it wrong. But I got as a result that we're only ~5 OOM away from the
theoretical limits.

1000 single bit operations per FLOP

jzbiciak — 2008-06-23T07:07:35+00:00

Regarding the multiplier... It turns out that floating point multipliers can get rid of most of the alignment steps that the adder needs to do. (See my other post.) You also don't need to apply the sign to your input or your output. So, you're just left with the addition steps.

A naive 24 × 24 multiplier would effectively do 24 24-bit adds. That's 6336 SBOPs. Assume for a moment, though, that we can eliminate about half of those because only 24 output bits are needed. This brings us down to 3168 SBOPs for the multiplier. Remaining steps:

Adding the mantissas: 88 SBOPs.
Aligning the result (shift by up to 3 positions, IIRC, implemented as 2 levels of 2:1 mux): 2 × 24 × 3 = 144 SBOPs

This gives a total of ~3400 SBOPs. About 2× to 3× the cost of an adder.

Oh, and that reminds me, you can eliminate one of the argument inversions in my adder estimate above. That squeezes another 60-70 SBOPs out. (You do add some other bit inversions here and there on the sign bits, which is why you don't get all 72 back.)

1000 single bit operations per FLOP

jzbiciak — 2008-06-23T06:56:56+00:00

First, let's assume that each computation is done in the minimum number of steps possible. Many of the transistors spent in functional units today are spent on making a single copy of the operation go faster. When computing at an atomic scale, this probably no longer makes sense. It probably makes more sense to make each operation as simple and economical as possible so you can put down as many copies as you like precisely where they're needed.

With volume computing you'll have so much more connectivity to neighbors that economical implementations would likely win out. For instance, a carry-select adder, which computes two versions of the result speculatively and throws away one, wouldn't make sense since it's much, much larger than a ripple-carry adder. (IIRC, a state of the art 32-bit adder is around 3000 transistors, whereas a 32-bit ripple carry adder should be around 700 or so.)

A 1 bit full-adder—3 inputs, 2 outputs—consists of two pieces: The sum computation, which is two two-input XOR gates, and the carry computation, which is 3 two-input AND gates and 2 two-input OR gates. The logic equations are:

sum_out = a XOR b XOR carry_in
carry_out = (a AND b) OR (a AND c) OR (b AND c)

If you assume a ripple carry implementation, then that's it. 7 operations per bit if you allow the full complement of boolean operations. So, a 32-bit add will be a mere 224 boolean operations. Even if you penalize XOR and count them as 3 bit operations each, that's still only 352 boolean operations. Of course, IEEE-754 floating point isn't built around 32-bit adds. You go through the following major steps for a single-precision floating point addition:

(For now I assume a parallel implementation since it doesn't really affect the number of SBOPs. Also, I assume the more conservative 11 SBOP number for a single bit full adder.)

Subtract the mantissas to get the "alignment difference" between the two numbers. This is an 8 bit subtract, IIRC, so would cost 88 SBOPs.
Shift the numbers to align them. To be conservative, I'll say this comprises the following steps in a simplistic implementation:

Swap the two numbers based on the sign of the difference of the magnitudes. This requires 24 2:1 muxes, and each 2:1 mux costs 3 SBOPs, for a cost of 2 × 24 × 3 = 144 SBOPs.
Shifting the smaller magnitude number to the right by up to 24 positions. If you structure this as 5 layers of 2:1 muxes (which is overkill, since some of the inputs will be zero and so this could be optimized), you get 5 × 24 × 3 = 360 SBOPs.

Apply the sign to both numbers. IEEE-754 is stored in sign-magnitude form. To apply the sign, you merely need to XOR the number with the sign and inject an appropriate carry when you do the addition. Thus, we can estimate this as 48 XORs, which, if you count XOR as 3 SBOPs, is 144 SBOPs.
Actually add the two 24 bit mantissas. If we go with 11 SBOPs per bit, this is 264 SBOPs.
Strip the sign from the result. Again, you could simply XOR with the result's sign bit (which should be the carry out of the last adder). 3 × 24 = 72 SBOPs.
Count the number of leading zeros so that we can renormalize the result. I don't know off the top of my head how many SBOPs this ought to take.
Shift the final result to normalize it. Conservatively, let's use the crummy shifter above which is 5 × 24 × 3 = 360 SBOPs
Update the mantissa. This is another 8-bit add. 8 × 11 = 88 SBOPs.

So where does that put us in this really basic, if perhaps naive implementation? Around 1520 SBOPs plus the cost of the priority encoder used for normalization.

Sure, we haven't handled overflow, underflow, denormals, NaNs and so on. But, I also have assumed clumsy implementations for some of the more expensive bits, such as the shifters. If the shifters were half the cost, for example, the total drops to 1160. Overall, I'd say this quick and dirty analysis validates that Val's SWAG (Scientific Wild Ass Guess) is in the right ball park, and certainly well within an order of magnitude. Since nearly all the rest of the numbers are expressed in orders of magnitude, being off by 50% ain't so bad. The log10 of 1.5 is pretty small.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

jzbiciak — 2008-06-23T06:05:47+00:00

I imagine an ultimate laptop would look more like a dataflow machine of some sort where
functional units are connected directly to neighboring functional units rather than time
multiplexing instructions through a smaller set of functional units with all the overhead you
describe.

After all, with that many compute elements, why wouldn't you?  I imagine data storage would
largely return to a delay element model too, just for its compactness.  Since compute elements
would be in contact with all the data elements at any given time, you could easily access all
of your data in parallel and do *something* with it, even if it's just moving it along.  The
sheer dynamics of such a dense system would mean that the data has to keep moving though.

Power usage?

jzbiciak — 2008-06-23T06:00:23+00:00

There sure are. One of the papers apparently describes a simple 8-bit reversible CPU.

Kurzweil

wahern — 2008-06-21T00:25:24+00:00

I haven't read the book, but it seems to me that the point is that certain advancements in
computation are universal, and previous industries can be considered as serial advancements in
(or facilitators of) general computational capabilities. So it doesn't matter that
advancements in steam engines were finite; rather that subsequent advancements made possible
by steam engines, no matter the material industry, had the effect of in kind furthering
[exponential] growth in computational capabilities in general.

Theoretical computational advancement can continually progress as long as materials science,
no matter how disjoint, continually provides sufficient capabilities for the realization of
the next rung on the theoretical ladder.

The overall argument is not particularly persuasive, I agree, but not obviously fallacious.

Hmm... H-bar? What's the problem with it?

dvdeug — 2008-06-20T22:49:55+00:00

The last browser that had any problem with that was Netscape 4. (No, lynx handles it just
fine.) Basic Latin characters used by major European languages (like Maltese) are supported by
everyone and have been for a long time.

1000 single bit operations per FLOP

mikov — 2008-06-20T17:42:41+00:00

I wonder how accurate the 1000 single-bit operations estimation is. Mind you, I am not a
electronic design expert, so this is just rambling. 

I've been thinking that a 1-bit adder has three inputs, so it has a 8-entry truth table. (Each
entry looks like something like "o=i1 & ~i2 & i3").
After optimizations, I am counting 18 single bit operations ("ands" and "nots"). It has two
outputs, I guess that is just double the whole thing  to 36.

So for a 32-bit integer adder we have 32*36=1152 single-bit operations operations. The
straight-forward multiplier, which they thought us in school, will do an addition per set bit,
so  if we assume 16 set bits on average, we get 18432 single bit ops, ignoring the shifts.

So, when using the most simplistic algorithms, the 1000 operations number seems far too
optimistic. 

Can someone do a similar estimation for the super-clever algorithms they actually use the CPUs
? (There is a detailed description in "Computer Architecture: A Quantitative Approach", but I
never understood it well enough to actually keep it in my head, and the book is not with me.
Oh yes, and I am lazy)

Academic compression

mtorni — 2008-06-20T14:40:30+00:00

If you drop the optional qualifier you can increase the (already lossy) compression and
achieve a notable compression with a tiny loss in useful resolution.

Power usage?

epa — 2008-06-20T08:39:30+00:00

I was just thinking of normal, non-reversible computation, constrained to dissipate at most
one watt of heat.

Do any reversible computing devices currently exist?  (Yes, I know a NOT gate exists, but I
mean something computationally more powerful than that, preferably Turing-machine-equivalent,
and specially designed to use the properties of reversible computation to minimize power
consumption.)

gravitational constant is G not g

stuart_hc — 2008-06-20T03:27:35+00:00

A small point, but the gravitational constant by convention is written with a capital G not a lowercase g.

Hmm... H-bar? What's the problem with it?

leoc — 2008-06-19T22:33:58+00:00

Why not render the equations with tex as god intended.

Hmm... H-bar? What's the problem with it?

kraney — 2008-06-19T21:13:17+00:00

That's funny, given that HTML was invented by a physicist for the purpose of sharing physics 
papers. Everyone else is a squatter.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

vaurora — 2008-06-19T17:22:21+00:00

In the original article, the author makes it much more clear that we are assuming nothing
about what the technology of computers in the future looks like.  In particular, we're not
assuming that the storage of the computer is compartmentalized into a small box containing
spinning rust-covered disks. :) All the calculations are based solely on the mass and volume
of the computer, with no assumptions about distribution.

Hmm... H-bar? What's the problem with it?

vaurora — 2008-06-19T17:18:40+00:00

Thanks for the pointer!  Due to the browser compatibility issues, I'll stick with
well-supported symbols.  HTML is not the ideal medium for physics.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

vaurora — 2008-06-19T17:16:30+00:00

Yes, that's an error - thank you for catching it!  The correction is on the way.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

bobort — 2008-06-19T17:02:39+00:00

The number of SBOPs per FLOP has not been constant over time, and it isn't really obvious how
that's going to change in the future.  Remember you have to account for all of the control
infrastructure, which dwarfs the arithmetical logic on a modern CPU - thousands of
multiplexers, comparators, buffers, lookup tables, signal repeaters, etc. just to get the data
from memory to the ALU and back - and the trip gets farther every year.  I suspect there are
more like 100k SBOPs per FLOP in a typical CPU, but that's a guess.

Will things get more or less "efficient" over time?  It's very hard to say, there are powerful
forces pulling in both directions.  I'd say the biggest undetermined aspect is whether we can
weasel around Amdahl's law, or how much.  How parallelizable will the software running on the
ultimate laptop be?  If everything ends up being highly parallelized, microarchitecture is
likely to evolve towards simplicity and SBOPs per FLOP will probably stay roughly the same or
even come down a bit.  If nobody comes up with a way around Amdahl (which is a rigorous
theorem unlike Moore's "law"), single-thread performance will need to be continually
increased, and that will increase SBOPs per FLOP over time.

Accademic compression

utoddl — 2008-06-19T15:20:48+00:00

This nicely ties back to the compression discussion above, as the accademic compression technique can squeeze an entire semester's work down to a single letter and an optional "+" or "-" qualifier.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

nix — 2008-06-19T13:40:34+00:00

As an aside, if you want to consider even higher physical limits by making the computer as
dense as you possibly can in order to push up its mass and energy density, you start getting
into really interesting and bizarre stuff applying to black-hole-density computational
devices, like the holographic principle and the Bekenstein bound.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

nix — 2008-06-19T13:35:33+00:00

I find Vinge's original concept of the technological singularity to be much more interesting
than Kurzweil's accelerating-progress thing, which suffers from severe selection bias: had he
written that book in 1920, it would have been obvious that an avionics singularity was
approaching by, say, 1990. It didn't happen, because progress in single technological fields
follows S-shaped curves, not exponential ones.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

nix — 2008-06-19T13:32:13+00:00

The ultimate laptop looks like a thermonuclear explosion? If only! There's lots of actual
organized matter in that (e.g. it's not all monatomic hydrogen plasma so there's order in the
nuclei).

It's more like the aftermath of a total annihilation reaction: a blast of elementary particles
and wide-spectrum (mostly high-energy) radiation, all, of course, precisely positioned so that
it interacts neatly.

The engineering challenges involved in building this thing are significant :) and how you do
I/O I have not the least idea. I imagine you'd need smaller computers to mediate between the
ultimate laptop and anything else. This is post-Transcend stuff ;}

(Oh, and, er, why does this need to be on a kernel hacker's bookshelf exactly? I know the life
of a Linux kernel hacker is an exciting and never-ending whirl, but I didn't think it was
*this* exciting.)

Not just the ultimate compression algorithm

alankila — 2008-06-19T13:21:50+00:00

Fascinating article. Thanks a lot for writing it.

The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation

dskoll — 2008-06-19T13:12:49+00:00

Yes, Kurzweil's book does have the tone of religious fervour.  I'm not saying I agree with
everything he says, just that the book was interesting.

I'd read it more as a science-fiction extrapolation that non-fiction.

Power usage?

emk — 2008-06-19T12:02:14+00:00

Basically, if you're worried about power and heat, you want to know the fundamental limits of reversible computation. A reversible computation is, of course, a reversible machine, and therefore uses no energy (except for output bits). Richard Feynman actually wrote a nice essay on this problem. And as it turns out, you can still do an insane amount of computation per unit time, under the laws of physics.

Of course, it's probably impossible to actually construct a true reversible machine, although certain small-scale quantum phenomenon, such as superconductivity, come surprisingly close.

Not just the ultimate compression algorithm

emk — 2008-06-19T11:54:14+00:00

Such a time machine also allows you to send bits back in time. Let's say you want to know whether the Cubs win the World Series sometime between now and 2107. Simply create a file named "yes-they-won.txt". If the Chicago Cubs win, access that file. Presto! Your "compression" algorithm can now be used to tell whether or not the victory occurred / will occur.

If you want to place bets, create 100 files named "2008", "2009", "2010", etc. Then, at the beginning of each year the Cubs win the World Series, max out your credit cards and stake your entire fortune on the Cubs winning.

But this turns out to be an amazing waste of your "compression" algorithm. As it turns out, once you can send bits back in time, you can build a negative time delay element, a circuit component that shifts its inputs back in time. This, in turn, allows you solve NP-complete problems in polynomial time, as described in the Moravec article I just linked.

And if NP is equal to P, then you've built something much more powerful than a quantum computer. Specifically, you can answer virtually any question you can ask, provided the correctness of that answer can be checked in polynomial time. And this, in turn, has further surprising consequences:

But another reason we believe P≠NP is that otherwise mathematical creativity could be automated! You'd simply ask your computer: "Is there a proof of the Riemann hypothesis with at most a million symbols?" And if there is such a proof, the computer will find it in some way dramatically faster than searching through every possibility. If P=NP, you wouldn't merely have solved one of the seven million-dollar problems from the Clay Math Institute -- presumably you could also solve the other six.

(See also the section titled "Linearity" in another of Scott Aaronson's lectures, which links to a paper analyzing a number of related problems in physics.)

Kurzweil

Hanno — 2008-06-19T11:17:42+00:00

You missed the book suggestion

I read it and found it interesting and tiring.

the exponential growth we are seeing now

...would only be "exponential" if it continued. Previously in history, humanity experienced a short period of exponential growth in steam, plastics, atomic power. Where is that exponential innovation now?

Painting this as a trend for two billion years is the result of cherrypicking datapoints.

Typo

corbet — 2008-06-19T11:05:55+00:00

What if it's a really big university?

Clearly a typo, I'm not quite sure how we missed it. Fixed now.

Kurzweil

corbet — 2008-06-19T11:03:12+00:00

You missed the book suggestion - it is a worthwhile read - at least much of the first half of it is. One of the things he asserts is that the exponential growth we are seeing now is not "present development"; it is, instead, a trend which has been going on for a good two billion years. Contemporary electronics is just the current substrate upon which the growth of complexity is being carried out.

The notion of the singularity, incidentally, is not necessarily as utopian as you suggest here.

I'm not saying that arguments like Kurzweil's are necessarily correct - no doubt there's plenty of ways to poke holes in them. But it's best to understand them first.