  Suppose that we are given a function f : (0,1) -> (0,1) and, for some unknown
p in (0,1), a sequence of independent tosses of a p-coin (i.e., a coin with
probability p of ``heads'').
  For which functions f is it possible to simulate an f(p)-coin?; This question
was raised by S. Asmussen and J. Propp. A simple simulation scheme for the
constant function 1/2 was described by von Neumann (1951); this scheme can be
easily implemented using a finite automaton. We prove that in general, an
f(p)-coin can be simulated by a finite automaton for all p in (0,1), if and
only if f is a rational function over Q. We also show that if an f(p)-coin can
be simulated by a pushdown automaton, then f is an algebraic function over Q;
however, pushdown automata can simulate f(p)-coins for certain non-rational
functions such as the square root of p. These results complement the work of
Keane and O'Brien (1994), who determined the functions $f$ for which an
f(p)-coin can be simulated when there are no computational restrictions on the
simulation scheme.
