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]

Flaw in proof?

At cs.SE the proof as given in this article is discussed, and some parts seem to be incorrect or incomplete according to the discussion. Please improve if you are knowledgeable about the subject. https://cs.stackexchange.com/questions/104982/proof-of-space-hierarchy-theorem-incompatible-with-linear-speed-up-theorem-for-t/105282 Hermel (talk) 22:17, 28 December 2019 (UTC)[reply]