Simulating nondeterministic space-bounded computation using randomness Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer yes when $x \in L$ with $\Pr(yes) &gt; 1/2$ and answer no when $x \not\in L$ with $\Pr(no) = 1$? Let's suppose I dont care about time as long as the machine halts.
My comment was incorrect, and in fact the answer to your question is YES. From Wikipedia: 


  Suppose C is the complexity class of
  problems solvable in logarithmithic
  space with probabilistic Turing
  machines that never accept incorrectly
  but are allowed to reject incorrectly
  less than 1/3 of the time; this is
  called one-sided error. The constant
  1/3 is arbitrary; any x with 0 ≤ x &lt;
  1/2 would suffice.
  
  It turns out that C = NL. Notice that
  C, unlike its deterministic
  counterpart L, is not limited to
  polynomial time, because although it
  has a polynomial number of
  configurations it can use randomness
  to escape an infinite loop. If we do
  limit it to polynomial time, we get
  the class RL, which is contained in
  but not known or believed to equal NL.