For the discrete version, doesn’t this boil down to converting a program that semi-computes a semi-measure into a program that “semi-samples from” a semi-measure?
Which is pretty straightforward:
We interpret the remainder of our (infinite) input as a real number y in [0,1]. Every time the measure that we’re semi-computing adds an amount p of probability to one of its possible values v, we increment a variable x (which was initialised to 0) by p. If and when x finally exceeds y, we return the value v whose probability was just incremented.
(The continuous version, which is the one we actually need, looks harder, but I guess the same general idea should work. Perhaps we just repeat the algorithm above once for every bit of the output?)
For the discrete version, doesn’t this boil down to converting a program that semi-computes a semi-measure into a program that “semi-samples from” a semi-measure?
Which is pretty straightforward:
We interpret the remainder of our (infinite) input as a real number y in [0,1]. Every time the measure that we’re semi-computing adds an amount p of probability to one of its possible values v, we increment a variable x (which was initialised to 0) by p. If and when x finally exceeds y, we return the value v whose probability was just incremented.
(The continuous version, which is the one we actually need, looks harder, but I guess the same general idea should work. Perhaps we just repeat the algorithm above once for every bit of the output?)