A mathematical theory of randomized computation. I
type: Item
instance of: scholarly article
title: A mathematical theory of randomized computation. I
zbMATH Open document ID: 0657.68061
author: Shinichi Yamada
published in: Proceedings of the Japan Academy. Series A
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D99
Mathematics Subject Classification ID: 46B42
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4074499
zbMATH Keywords: randomized computation
zbMATH Keywords: probabilistic algorithms
zbMATH Keywords: randomized algorithms
zbMATH Keywords: domain theory
zbMATH Keywords: denotational semantics
zbMATH Keywords: probabilistic programming languages
zbMATH Keywords: machine learning
zbMATH Keywords: algorithmic information theory
zbMATH Keywords: Banach lattices
zbMATH Keywords: spaces of bounded measures
MaRDI profile type: Publication
full work available at URL: pjaa.64.115
OpenAlex ID: W2078359033
cites work: Concrete representation of abstract (M)-spaces. (A characterization of the space of continuous functions.)
cites work: Q5649639
cites work: Data Types as Lattices
cites work: Minimal tori in \(S^ 3\) whose lines of curvature lie in \(S^ 2\)
DOI: 10.3792/PJAA.64.115
description: scientific article; zbMATH DE number 4074499