Content deleted Content added
AmirOnWiki (talk | contribs) Deterministic time hierarchy theorem: some cleanup and replacement of broken link to lecture notes by link to book |
AmirOnWiki (talk | contribs) →Proof: minor fix of argument |
||
Line 114:
Here, ''M'' is a deterministic Turing machine, and ''x'' is its input (the initial contents of its tape). [''M''] denotes an input that encodes the Turing machine ''M''. Let ''m'' be the size of the tuple ([''M''], ''x'').
We know that we can decide membership of ''H<sub>f</sub>'' by way of a deterministic Turing machine ''R'', that simulates ''M'' for ''f''(''x'') steps by first calculating ''f''(|''x''|) and then writing out a row of 0s of that length, and then using this row of 0s as a "clock" or "counter" to simulate ''M'' for at most that many steps. At each step, the simulating machine needs to look through the definition of ''M'' to decide what the next action would be. It is safe to say that this takes at most ''f''(''m'')<sup>3</sup> operations (since it is known that a simulation of a machine of time complexity ''T''(''n'') for can be achieved in time
: <math> H_f \in \mathsf{TIME}\left(f(m)^3\right). </math>
| |||