Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this computer sample from, provided that your program must terminate after finitely many steps (not almost surely, but logically must terminate)?

For a simpler example, if your computer can sample a 'fair coin', heads 1/2 and tails 1/2, then it can also sample any binary event with probability a dyadic rational: $p/2^n$, $0 \leq p \leq 2^n$ an integer. It can't sample an event with probability $1/3$. The program "Flip two coins, $HH$ is a success, and on $TT$ repeat the experiment" is not allowed because it is not guaranteed to terminate (even though it will terminate with probability $1$).

Since it might be hard to characterize 'all possible' distributions, here's a concrete question: Can you sample from the Haar measure on any compact matrix Lie group?

EDIT: The idea of a random real number has more philosophical and practical subtleties than I realized when posting this question. I encourage commenters to answer based on varying interpretations, but to get the ball rolling how about these restrictions:

1) Given random real numbers x and y, the computer can calculate x + y, xy, and x/y (provided y =/= 0) in one step. (You can also multiply/add/divide by rational numbers)

2) Given a real random number x, the computer can decide in one step if x > 0, x = 0, or x < 0 and act accordingly.

I know this might not accurately model how computers or computer models work, so like I said feel free to play with these assumptions.

3more comments