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]

Corollary 2- real number argument

I have discussed with others about the validness of corollary 2 and it seems to us that this statement is wrong. For any positive real number $a$ there would be a language that is in $Space(n^{a})$ , but not in $Space(n^{b})$ for any $b<a$ . Any language in $Space(n^{a})$ is decidable by definition, so we would have uncountably many languages. But there are only countable many decidable languages, so this result can't be true. It is also not a direct corollary to corollary 1, as with a similar argument $n^{a}$ is not computable and by that not space-constructible for arbitrary real $a$ .

I am missing something ? JT0202 (talk) 14:11, 15 December 2023 (UTC)[reply]