Time hierarchy theorem: Difference between revisions

Revision as of 06:03, 19 March 2022

Revision as of 15:49, 25 March 2022

Line 112:

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 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 knowknown 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>