EQUIVALENCES BETWEEN PROBABILISTIC AND DETERMINISTIC SEQUENTIAL MACHINES
MICHIGAN UNIV ANN ARBOR COLL OF LITERATURE SCIENCE AND THE ARTS
Pagination or Media Count:
The concept of probabilistic sequential machines PSM, a generalization of Rabins 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.
- Numerical Mathematics