Time hierarchy theorem: Difference between revisions

Revision as of 17:57, 28 August 2021

Revision as of 17:23, 1 September 2021

Line 110:

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_f'' by way of a deterministic Turing machine ''R'', that simulates ''M'' for ''f''(''x'') steps by first calculating ''f''(|''x''|) and then 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'')³ operations (since it is know that a simulation of a machine of time complexity ''T''(''n'') can be achieved in time ''O(''T''log''T'')''), we have that:

: <math> H_f \in \mathsf{TIME}\left(f(m)^3\right). </math>