Talk:Space hierarchy theorem
|WikiProject Mathematics||(Rated Start-class, Mid-priority)|
In the note on step 3: " Execution is limited to 2^f(|x|) steps in order to avoid the case where M does not halt on the input x... That is, the case where M consumes space of only O(f(x)) as required, but runs for infinite time. "
If M does not halt on input x it does not accept x. The algorithm for deciding L should therefore accept in case more than 2^f(|x|) were made, as M does not accept <M>,10^k, and <M>,10^k is therefore in L, from the definition. —Preceding unsigned comment added by 188.8.131.52 (talk) 06:31, 1 March 2009 (UTC)