Is there any existing literature on applying the theory of Type-2 computability to the generation of random variates? By “random variate generator” I mean a computable function $ f\colon\subseteq\{0,1\}^{\omega}\rightarrow D$ such that, if $ p$ is a random draw from the standard (Cantor) measure on $ \Sigma^{\omega}$ , then $ f(p)$ is a random draw from a desired probability distribution on $ D$ . Think of $ f$ as having access to an infinite stream of random bits it can use in generating its output value. Note that $ f$ need not be a total function, as long as its domain has (Cantor) measure 1.
It seems to me that the way to proceed would be to require that one specify a topology on $ D$ , in fact a computable topological space [1] $ \boldsymbol{S}=(D, \sigma, \nu)$ where $ \sigma$ is a countable subbase of the topology and $ \nu$ is a notation for $ \sigma$ , and use the standard representation $ \delta_{\boldsymbol{S}}$ of $ \boldsymbol{S}$ . One might also want membership in the atomic properties $ A\in\sigma$ to be “almost surely” decidable; that is, there is some computable $ g_A\colon\subseteq\{0,1\}^{\omega}\rightarrow\{0,1\}$ whose domain has measure 1, such that
$ $ g_A(p) = 1 \mbox{ iff } f(p)\in A$ $
whenever $ p\in\mathrm{dom}(g_A)$ .
I’m working on a problem that needs a concept like this, and I’d rather not reinvent the wheel if this is a concept that has already been well explored.
[1] See Definition 3.2.1 on p. 63 of Weihrauch, K. (2000), Computable Analysis: An Introduction.