Talk:Space hierarchy theorem

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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]