Mental Exercise

[James Joseph Clark]

Just to put my two cents in:

> 
>    FlavorMaus at aol.com wrote:
>    > sorry, a machine is incapable of true randomness.
>      
> 

This validity of this statement depends on the definition of
"machine". Care must be taken that this definition does not render the
above statement tautalogical. I challenge you to come up with a
non-trivial one. Even if you do come up with such a definition of
machine, you would never find a physical instantiation of such a
machine in our world. Physical "machines" must neccessarily be built
from physical structures which, at some level, will themselves not
adhere to this definition of a "machine".

One can construct a deterministic state machine from a finite set of
physical logic gates whose complete state sequence is nonetheless
indeterminable, due to the fact that you cannot completely know the
state of the physical structures that comprise the state machine and
due to the unavoidable influence of the environment. This cannot be
analyzed as a finite state machine (due to the influence of "external"
factors), but is still physically realizable. For example, one can
arrange the circuit so that minute variations in timing (propagation
delays and so form) give rise to completely unpredictable state
sequences. No explicit external inputs are required for this. Of
course if you have external inputs, then it is much easier to produce
unpredictable inputs (e.g. the trick of using wall-clock time to seed
a random number generator). One reason why designing and verifying
"embedded" systems is difficult is that the lack of control over the
external inputs leads to non-finite automata, which are much harder to
analyze than finite automata.

Jim
clark at cim.mcgill.ca