Accession Number : AD0463885
Title : EQUIVALENCES BETWEEN PROBABILISTIC AND DETERMINISTIC SEQUENTIAL MACHINES
Descriptive Note : Technical rept.
Corporate Author : MICHIGAN UNIV ANN ARBOR COLL OF LITERATURE SCIENCE AND THE ARTS
Personal Author(s) : Page, C V
Report Date : Apr 1965
Pagination or Media Count : 79
Abstract : The concept of probabilistic sequential machines (PSM), a generalization of Rabin's concept of probabilistic automata, is defined. Such diverse devices as unreliable digital computers, slot machines, and chemical cells are presented as examples of PSM. Using the examples as motivation, various kinds of equivalences between machines are discussed. The fundamental question of when a PSM is equivalent in some sense to a deterministic machine, perhaps with random devices attached to output states, is considered. Finally, various tests involving finitely many random variables are devised for each of the kinds of equivalences between PSM and for reduction, if possible, to deterministic machines. One of the tests is a further generalization of the Moore bound for deterministic machines than has previously appeared in the literature.
Descriptors : *DETERMINANTS(MATHEMATICS) , INPUT OUTPUT DEVICES , AUTOMATA , SEQUENCES(MATHEMATICS) , GRAPHS , SET THEORY
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE