Content deleted Content added
mNo edit summary |
m typo |
||
Line 128:
We use this ''K'' to construct another machine, ''N'', which takes a machine description [''M''] and runs ''K'' on the tuple ([''M''], [''M'']), ie. M is simulated on its own code by ''K'', and then ''N'' accepts if ''K'' rejects, and rejects if ''K'' accepts.
If ''n'' is the length of the input to ''N'', then ''m'' (the length of the input to ''K'') is twice ''n'' plus some delimiter symbol, so ''m'' = 2''n'' + 1. ''N''
:<math> \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f\left( \left\lfloor \frac{2n+1}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f(n)\right). </math>
| |||