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


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/463885.pdf


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