EQUIVALENCES BETWEEN PROBABILISTIC AND DETERMINISTIC SEQUENTIAL MACHINES
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1965
- Accession Number
- AD0463885
Entities
People
- C. V. Page
Organizations
- University of Michigan