Peter Trei writes:
> ...
> How difficult would it be to build a mechanical
> shuffling machine, with enough randomness to
> produce a good shuffle? Even the best card
> magicians in the world have difficulty in
> performing more than a few perfect shuffles in
> a row. In the absence of a machine, let several
> neutral judges take turns shuffling the deck a
> few times.
> ...
Actually, it's surprisingly hard to build a really good mechanical
shuffling machine. A mechanical device is just another way to express
an algorithm. You have all the same problems you have devising a
mathematical algorithm in the first place, plus you have to deal with
the issues of how to implement that algorithm, and of dealling with
real-life mechanical error in the implementation. The problem with
those errors as that they won't be "true random", but are instead
likely to be strongly correlated with very non-random stuff. Knuth
does a good job of showing how combining two bad random number
generators makes a worse one; this is just as true of mechanics as it
is of math. This is why people (who are, after all, frightfully
complicated) are bad at things like making up random sequences of
numbers.
The simplest mechanical device I can think of would be just one of
those "shuffling" robots they used to have at carnivals.
Unfortunately, this is only useful for card tricks; the problem is that
the classical shuffling algorithm is bad enough at randomizing things
that the patterns that persist can be used for tricks. The
machine is probably going to be even less random than the human.
A more complicated approach might be the lottery approach. In one
typical expression of this, there is a transparent container containing
a bunch of ping-pong balls with numbers on them, being blowing around
with compressed air inside a transparent container. After they've been
bouncing around for a while, a passage is opened, and the first ball
(or N balls) out is the sample. Put 52 balls in, numbered 1-52,
associate each with a card, and you have your order. I suppose if you
wanted something even more complicated you could have a photoelectric
reader read the number off the ball and print a custom deck in the
appropriate "random" order. I talked to one person who claimed even
these devices aren't actually very random either, and that the state
lotteries that use these have a noticeable bias to them. I don't know
if they were right or not, but I can think of some obvious ways for
errors to creep in. For instance, the balls probably aren't all
exactly the same weight. Ping-pong balls are, after all, not a high
percision device; they're probably quite round, but I wouldn't be
surprised at a weight variance of 10%. Also, those numbers painted
on them probably do things to the weight, and also the friction as they
bounce and spin. It does look cool on TV however.
Now, a really entertaining idea might be to construct something that
mechanically implements SHA-1, with all sorts of sliding levers and
things, followed by a bank of 51 mechanical dividers daisy-chained to
each other, for computing N modulo 52, 51, 50, etc. (I suppose you
could get away with just one divider, but 51 is so much more fun.)
You'd still need a source of input randomness -- I suppose the front
page of the New York Times would do; if typing that in is too much
effort, the stock market seems to generate lots of noise. If there
were ever any question about whether the mechanical gadget was
functioning correctly, you could double-check its answer with a laptop
and the same data.
Then, there is the classical approach. For instance, borrow one of the
german Enigma's from the smithsonian, get it running, and devise some
sort of "secure" hash based on its output. Then, all you need are
several germans dressed up in 19th century prussian uniforms to read
the new york times, operate the thing, record and post-process the
output (using an adding machine?) and sort the deck in the requisite
order. It should be quite a show, if done right.
If you don't mind a bit of blood, there is the biological approach.
Take several frogs, and "harvest" the hearts, hooking them up in
the right apparatus to beat for a few hours. Each should continue
to beat. Use random long-term variations in rate to generate entropy
and proceed accordingly. For extra credit, harvest the nerve tissue
also and construct a crude logic circuit to collect the entropy.
-Marcus Watts
UM ITD PD&D Umich Systems Group
