Talk:Space hierarchy theorem

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 132.74.99.86 (talk) 06:31, 1 March 2009 (UTC)[reply]