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