Time hierarchy theorem: Difference between revisions

Revision as of 05:02, 30 January 2023

Revision as of 12:06, 7 February 2023

Line 109:

: <math> H_f = \left\{ ([M], x)\ |\ M \ \text{accepts}\ x \ \text{in}\ f(|x|) \ \text{steps} \right\}. </math>

Notice here that this is a time-class. It is the set of pairs of machines and inputs to those machines (''M'',''x'') to those machines so that the machine ''M'' accepts within ''f''(|''x''|) steps.

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'').