title: How does an oblivious Turing machine work?
body: <p>I am reading the book <strong>Computational Complexity: A Modern Approach</strong> and I am having problems understanding <strong>oblivious Turing machines</strong>.</p>
  
  <p>An oblivious Turing machine (TM) is such a TM that the movement of its heads is entirely determined by the <strong>length of the input</strong>. That is, the TM is oblivious to its input. So far so good.</p>
  
  <p>But one of the excercises is to prove the following theorem:</p>
  
  <pre><code>If a language L is decidable in time T(n) 
  then there exists an oblivious TM that decides L in time O(T(n)^2). 
  </code></pre>
  
  <p>It is obvious that the oblivious TM must not operate on the original input of <code>L</code> but at some <em>coded</em> version. That is, the gist of the theorem is the <em>coding</em> of a <strong>bitstring</strong> to an <strong>integer</strong> (length of the input of the oblivious TM). But if one would want to code the set of possible inputs of <code>L</code> (bitstrings) to an integer, one would  run into very high numbers fairly quickly since there are <code>2^n</code> bitstrings of length <code>n</code>.</p>
  
  <p>Am I understanding the problem correctly? How do you prove the theorem?</p>