Content deleted Content added
→Proof: Fixed a sentence that ended prematurely. Replaced ‘halt within f’ by ‘halt within ''f''(|''x''|) steps.‘ |
→Proof: Replaced period with a colon. |
||
Line 110:
We include here a proof of a weaker result, namely that '''DTIME'''(''f''(''n'')) is a strict subset of '''DTIME'''(''f''(2''n'' + 1)<sup>3</sup>), as it is simpler but illustrates the proof idea. See the bottom of this section for information on how to extend the proof to ''f''(''n'')log''f''(''n'').
To prove this, we first define the language of the encodings of machines and their inputs which cause them to halt within ''f''(|''x''|) steps
: <math> H_f = \left\{ ([M], x)\ |\ M \ \text{accepts}\ x \ \text{in}\ f(|x|) \ \text{steps} \right\}. </math>
| |||