Provided a coinflip generator (a function that can be called to provide an output of either 1 or 0 with equal probability of $1/2$), is it possible to construct a function that would
yield either
a,borcwith equal probability of $1/3$, andhave well-defined memory requirements, runtime and guaranteed termination? (This point rules out running the coinflip two times for 4 outcomes and assigning one of the outcomes to re-run, because that is no longer guaranteed to terminate.)
This thought experiment appeared simple at first, but having given it some thought, I'm not sure this is possible, but I can't prove either case.
No, this is not possible. When you flip the coin $n$ times, you have $2^n$ equiprobable results. You want to divide them up equally among the $3$ outcomes, but $2^n$ is not divisible by $3$. Thus, no matter how often you throw the coin and no matter how you assign the outcomes, there will always be $1$ or $2$ outcomes left over. Thus, an algorithm that yields a probability of exactly $\frac13$ cannot be guaranteed to terminate; you can only minimize the expected number of coin flips you need to generate.