84:
74:
53:
22:
401:
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
157:
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. "
189:
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.
140:
161:
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: -->
399:
325:
277:
190:
351:
427:
447:
229:
480:
130:
475:
106:
211:
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
170:
191:
https://cs.stackexchange.com/questions/104982/proof-of-space-hierarchy-theorem-incompatible-with-linear-speed-up-theorem-for-t/105282
97:
58:
33:
21:
174:
39:
83:
457:
166:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
453:
356:
282:
234:
89:
73:
52:
197:
330:
405:
432:
214:
469:
461:
201:
178:
193:
102:
79:
429:
is not computable and by that not space-constructible for arbitrary real
15:
435:
408:
359:
333:
285:
237:
217:
101:, a collaborative effort to improve the coverage of
441:
421:
393:
345:
319:
271:
223:
163:,10^k is therefore in L, from the definition.
8:
19:
47:
434:
413:
407:
382:
358:
332:
308:
284:
260:
236:
216:
49:
231:there would be a language that is in
7:
95:This article is within the scope of
38:It is of interest to the following
14:
481:Mid-priority mathematics articles
207:Corollary 2- real number argument
115:Knowledge:WikiProject Mathematics
476:Start-Class mathematics articles
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
388:
375:
314:
301:
266:
253:
1:
462:14:11, 15 December 2023 (UTC)
202:22:17, 28 December 2019 (UTC)
109:and see a list of open tasks.
394:{\displaystyle Space(n^{a})}
320:{\displaystyle Space(n^{b})}
272:{\displaystyle Space(n^{a})}
497:
452:I am missing something ?
179:06:31, 1 March 2009 (UTC)
134:
67:
46:
141:project's priority scale
98:WikiProject Mathematics
443:
423:
395:
347:
346:{\displaystyle b<a}
321:
273:
225:
28:This article is rated
444:
424:
422:{\displaystyle n^{a}}
396:
348:
322:
274:
226:
162:,10^k, and <M: -->
433:
406:
357:
331:
283:
235:
215:
121:mathematics articles
439:
419:
391:
353:. Any language in
343:
317:
269:
221:
90:Mathematics portal
34:content assessment
442:{\displaystyle a}
224:{\displaystyle a}
169:comment added by
155:
154:
151:
150:
147:
146:
488:
448:
446:
445:
440:
428:
426:
425:
420:
418:
417:
400:
398:
397:
392:
387:
386:
352:
350:
349:
344:
326:
324:
323:
318:
313:
312:
278:
276:
275:
270:
265:
264:
230:
228:
227:
222:
181:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
496:
495:
491:
490:
489:
487:
486:
485:
466:
465:
431:
430:
409:
404:
403:
378:
355:
354:
329:
328:
304:
281:
280:
256:
233:
232:
213:
212:
209:
187:
164:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
494:
492:
484:
483:
478:
468:
467:
438:
416:
412:
390:
385:
381:
377:
374:
371:
368:
365:
362:
342:
339:
336:
316:
311:
307:
303:
300:
297:
294:
291:
288:
268:
263:
259:
255:
252:
249:
246:
243:
240:
220:
208:
205:
186:
185:Flaw in proof?
183:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
493:
482:
479:
477:
474:
473:
471:
464:
463:
459:
455:
450:
436:
414:
410:
383:
379:
372:
369:
366:
363:
360:
340:
337:
334:
309:
305:
298:
295:
292:
289:
286:
279:, but not in
261:
257:
250:
247:
244:
241:
238:
218:
206:
204:
203:
199:
195:
192:
184:
182:
180:
176:
172:
168:
159:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
451:
210:
188:
171:132.74.99.86
160:
156:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
165:—Preceding
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
470:Categories
327:for any
167:unsigned
139:on the
454:JT0202
194:Hermel
36:scale.
458:talk
338:<
198:talk
175:talk
131:Mid
472::
460:)
449:.
200:)
177:)
456:(
437:a
415:a
411:n
389:)
384:a
380:n
376:(
373:e
370:c
367:a
364:p
361:S
341:a
335:b
315:)
310:b
306:n
302:(
299:e
296:c
293:a
290:p
287:S
267:)
262:a
258:n
254:(
251:e
248:c
245:a
242:p
239:S
219:a
196:(
173:(
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
