A mathematical theory of randomized computation. I (Q1111027)

Algorithms with incorporate random input data and random choices are called randomized or probabilistic. The author suggests a new randomized domain theory which naturally extends \textit{D. S. Scott}'s theory for deterministic computation [SIAM J. Comput. 5, 522-587 (1976; Zbl 0337.02018)] and provides a denotational semantics for a class of high level probabilistic programming languages and is also applicable to machine learning and algorithmic information theory. The main definitions of the probabilistic algorithms are given in the present paper. Firstly a short review of Scott's theory is considered. In a randomized algorithm (or program) the state vector F composed of the program variables and random oracles is thought as a random (vector) variable x: (\(\Omega\),\({\mathcal A},\mu)\to (X,{\mathcal B})\) where X is the domain of computation. Thus a randomized program is considered as a linear operator mapping an input probability measure to the output subprobability measure. Further the author recalls some familiar results from the theory of Banach lattices and spaces of bounded measures. As the author states, a continuation of this paper will contain a fixed point theorem for randomized recursions.