title: If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?
body: <p>Assuming that f(n) >= n.</p>
  
  <p>If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.</p>