Hi all,

In a post from January 18, Wirt Atmar noted that he doesn't believe that
computers will reach the HAL 9000 level for at least another century. Two
reports of recent research may mean that Wirt will be discussing the
issue with his computer long before 2097. One report deals with progress
along conventional lines, and the other with practical progress in an
area that has long been of theoretical interest. Both articles are in the
17 January issue of _Science_.

First, in conventional computing, scientists at at IBM have gone one
fairly large step down the road to single-electron transistors:
transistors that operate on single electrons rather than on current flow.
(It's probably a mistake to call the device "transistors" at that point.)
The IBM process produces transistors 3nm on a side, about a tenth the
linear dimension -- and a hundredth the areal dimension -- of today's
best processes. There is a lot of work to do in scaling up the process,
but the technique eliminates the problem that today's designs face, that
of increasing power density when decreasing chip size. The full text of
the article is at
<http://www.sciencemag.org/cgi/content/full/275/5298/303> (which may
require registration to access).

Many problems that were intractible five to ten years ago are yielding to
nothing more than increased brute-force computing power. Voice
recognition is the type specimen here, with systems on the verge of
recognizing speaker-independent connected speech using algorithms with
performance that scales directly with processor speed. (Software
distributed with PowerPC-based Macintosh computers recognizes a couple of
hundred connected phrases specified in plain English with an 80-90%
success rate.)

Of course, recognition is not the same as understanding, and that's where
the second development comes in. In quantum computing, a technique that
was considered "blue sky" only three years ago, researchers at NIST (the
National Institute of Standards and Technology) have succeeded in
realizing some of the technique's potential in a remarkably simple
device: a circuit board about 10 inches on a side, several coils, and a
cup of coffee. Previous, less-successful experiments required a roomful
of expensive equipment. The full text of the article is at
<http://www.sciencemag.org/cgi/content/full/275/5298/307>. Quantum
computers are important because they can, in theory, carry out millions
of calculations simultaneously, using processes that are strikingly --
indeed, uncomfortably -- close to those that are postulated in some
theories of conciousness. The NIST device proves that the key theoretical
barrier to practical quantum computers can in fact be overcome, at least
to some degree.

The archetypical example for quantum computing is the problem of
factoring. All of today's factoring algorithms require exponential time,
which is why public-key cryptosystems based on 512- or 1024-bit keys are
considered absolutely secure for any practical purpose. (Almost all
public-key cryptographic systems rely on the difficulty of factoring
large numbers for their security.) A large-enough quantum computer could
do the job in polynomial time. To illustrate the difference, an
exponential-time algorithm applied to a 16-bit number requires 256 (2^8)
times more computing than the same algorithm applied to an 8-bit number.
A polynomial-time algorithm does the same calculation in twice the time
on a 16-bit number as on an 8-bit number. (The actual situation is
somewhat more complicated, but that's the general idea.)

HAL probably won't be around in 2001, but I wouldn't bet too heavily
against 2020.

-- Bruce Toback
[log in to unmask]