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)

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)

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)