Title :
On read-once vs. multiple access to randomness in logspace
Author_Institution :
Dept. of Comput. Sci., Hebrew Univ., Jerusalem, Israel
Abstract :
In the correct definition of randomized space-bounded computation, the machine has access to a random coin. The coin can be flipped at will, but outcomes of previous coin flips cannot be recalled unless they are saved in the machine´s limited memory. In contrast to this read-once mechanism of accessing the random source, one may consider Turing machines which have access to a random tape. Here, the random bits may be multiply accessed by the machine. The author demonstrates a very concrete sense in which multiple access to the random bits is better than read-once access to them: Every language accepted with bounded two-sided error by a read-once-randomized logspace machine can be accepted with zero error by a randomized logspace machine having multiple access to the random bits
Keywords :
Turing machines; stochastic automata; Turing machines; logspace; multiple access; random coin; random tape; randomized space-bounded computation; randomness; read-once-randomized logspace machine; zero error; Computer errors; Computer science; Concrete; Error correction; Power line communications; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113966