98:
88:
64:
31:
22:
190:
619:
If the number of steps is exact though, that raises new issues; we can see that K runs in time f(n), but how does N run in time f(n)? If it simulates K, there would be a slowdown. And it has the overhead of copying the input to produce the input for K, and inverting the result, which presumably can't
629:
That's phrased a lot better than what I said. Actually more than a constant factor is required if you have to copy the input. That's why the proof seems to imply big O notation, because the added 'constant factors' are ignored. It might actually be necessary for the proof for N to be an alterned
228:
I kind of agree with you that "it is a bit weak" to just say "it is safe to say", but I also believe this article should stick to the thing it is about. To prove that it is possible to simulate a Turing machine in ever-lower time bounds is another proof in itself and, quite frankly, doesn't belong
333:
in sublinear time, although it can read it in sublinear work tape space), so it's actually redundant, in the same way that requiring NP proof signatures to have polynomial size is redundant. It might still be useful to mention somewhere though, since it does effectively limit the power of the
277:
641:
This article is a great example of why proofs are problematic on
Knowledge. First, it's not clear whether or not this proof is original research. Second, it appears to be a simplified proof, in an attempt to teach the subject matter, rather than present facts.
215:
Proof looks basically OK. It needs a justification of how a Turing machine can simulate M in O(f(n)Âł); "it is safe to say" is a bit weak. The fact that f is time-constructible need to be used explicitly in the proof. Also, we need an article on
312:
The time heirarchy theorem has actually been proved for a much stricter bound. Specifically, TIME(o( f(n)/log(f(n)) )) is a strict subset of TIME(O(f(n)) -- sorry for the lack of pretty LaTeX. Lecture notes with proof
615:
This error is predicated on the assumption that the notation TIME(f(n)) includes implied big-O notation (TIME(O(f(n))) which I've seen in some definitions but I think in this case it's meant to imply an exact number of
599:
does not simplify to false. Since K_f cannot be altered to determine if it's input (M,x) runs in O(f(m)), it is necessary to show that N_f can be defined to run in <= f(n) steps for the contradiction to hold.
278:
Proof that a Turing machine can simulate the first n steps of another Turing machine in at most n log m time, where m is the length of the description of the second Turing machine and its input
714:
168:
704:
276:
and give the external link; but this runs the risk of the link breaking in future. One could always write a new article with this proof, but the title of that article would be huge...
620:
be done in zero time. It seems a constant factor needs to be accounted for somehow, but I'm pretty fuzzy on this. Can someone lay out the details of this part more pedantically?
204:
274:
709:
694:
460:
are not written very clearly. The justification for each step is 'implicit' and hides a mistake in the proof. It would be clearer to write something closer to
35:
699:
329:) lower bound on t(n). I can only think it must be because no smaller functions are time-constructible (a Turing machine can't even read an input of size
724:
158:
689:
120:
729:
719:
144:
684:
662:
317:. I'm sorry I don't have time to update the article myself, but I thought I'd at least drop a comment with the information and a link.
111:
69:
342:
I've never thought of this, but it sounds really interesting. Thanks for this, I'll add something to this effect to the article. â
220:
explaining why the concept is important and the exciting things you can do with functions that are not time-constructible.
44:
346:
217:
291:
21:
666:
605:
299:
199:
50:
97:
647:
532:)) // by runtime evaluation of N 3 and 4 are a contradiction.
232:
119:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
295:
103:
87:
63:
229:
here. Of course, one could remove the "it is safe to say" bit and just claim it's possible in
601:
643:
150:
678:
621:
335:
314:
670:
651:
624:
609:
590:
Unfortunately, writing it this way shows a clear mistake. In the accepting case,
302:
284:
116:
343:
281:
93:
221:
189:
485:) // by definition of
557:) // by definition of
184:
153:
in the banner shell. Please resolve this conflict if possible.
149:
This article has been given a rating which conflicts with the
15:
208:. It may contain ideas you can use to improve this article.
661:
Please give a citation. Where the strict part is proved?
587:// simplification of 2) 0 and 3 are a contradiction.
520:) steps // by 0) and 2) 4)
235:
115:, a collaborative effort to improve the coverage of
630:'copy' of K, not just a machine that simulates it.
268:
715:C-Class articles with conflicting quality ratings
320:
705:Knowledge level-5 vital articles in Mathematics
657:DTime(f(n)) strictly contained in DSpace(f(n))?
325:I often see this result stated with a linear (
8:
19:
58:
710:Start-Class vital articles in Mathematics
321:Where's the linear lower bound come from?
234:
695:Knowledge vital articles in Mathematics
60:
356:Contradiction Cases and Time vs Steps
7:
109:This article is within the scope of
202:by Knowledge editors, which is now
49:It is of interest to the following
700:Start-Class level-5 vital articles
415:(which we know it does in at most
371:(which we know it does in at most
151:project-independent quality rating
14:
725:Mid-priority mathematics articles
129:Knowledge:WikiProject Mathematics
690:Knowledge level-5 vital articles
188:
132:Template:WikiProject Mathematics
96:
86:
62:
29:
20:
423:) operations), this means that
379:) operations), this means that
163:This article has been rated as
263:
257:
245:
239:
1:
625:21:00, 20 February 2009 (UTC)
610:20:33, 20 February 2009 (UTC)
580:) // by definition of K 3)
508:) // by definition of K 3)
308:Stronger bound, link to proof
269:{\displaystyle f(m)\log f(m)}
123:and see a list of open tasks.
730:Old requests for peer review
720:C-Class mathematics articles
671:08:44, 8 January 2018 (UTC)
347:15:51, 3 October 2005 (UTC)
303:22:39, 9 October 2005 (UTC)
285:15:51, 3 October 2005 (UTC)
218:time-constructible function
746:
685:Start-Class vital articles
652:16:52, 11 March 2009 (UTC)
338:28 June 2005 16:59 (UTC)
162:
148:
81:
57:
386:(, ), so (, ) is not in
292:Universal Turing Machine
224:23:41, 2004 Jul 4 (UTC)
169:project's priority scale
456:) steps. Contradiction!
405:) steps. Contradiction!
112:WikiProject Mathematics
592:(N halts on N in : -->
270:
196:Time hierarchy theorem
271:
36:level-5 vital article
397:does not accept in
233:
135:mathematics articles
637:Textbook-like proof
565:runs on in <=
493:runs on in <=
296:User:Ben Standeven
266:
104:Mathematics portal
45:content assessment
512:runs on in : -->
212:
211:
183:
182:
179:
178:
175:
174:
737:
360:The cases here:
275:
273:
272:
267:
192:
185:
137:
136:
133:
130:
127:
106:
101:
100:
90:
83:
82:
77:
74:
66:
59:
42:
33:
32:
25:
24:
16:
745:
744:
740:
739:
738:
736:
735:
734:
675:
674:
659:
639:
588:
533:
439:
391:
358:
323:
310:
231:
230:
134:
131:
128:
125:
124:
102:
95:
75:
72:
43:on Knowledge's
40:
30:
12:
11:
5:
743:
741:
733:
732:
727:
722:
717:
712:
707:
702:
697:
692:
687:
677:
676:
658:
655:
638:
635:
634:
633:
632:
631:
617:
597:(Time(N)=f(n))
573:) steps) and (
534:
462:
458:
457:
437:
430:(, ), so (, )
406:
389:
357:
354:
352:
350:
349:
322:
319:
309:
306:
288:
287:
280:perhaps? :) â
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
214:
210:
209:
193:
181:
180:
177:
176:
173:
172:
161:
155:
154:
147:
141:
140:
138:
121:the discussion
108:
107:
91:
79:
78:
67:
55:
54:
48:
26:
13:
10:
9:
6:
4:
3:
2:
742:
731:
728:
726:
723:
721:
718:
716:
713:
711:
708:
706:
703:
701:
698:
696:
693:
691:
688:
686:
683:
682:
680:
673:
672:
668:
664:
663:89.177.144.33
656:
654:
653:
649:
645:
636:
628:
627:
626:
623:
618:
614:
613:
612:
611:
607:
603:
598:
594:
586:
583:
579:
576:
572:
568:
564:
560:
556:
552:
548:
545:
541:
538:
531:
527:
523:
519:
515:
511:
507:
504:
500:
496:
492:
488:
484:
480:
476:
473:
469:
466:
461:
455:
451:
447:
444:
440:
433:
429:
426:
422:
418:
414:
411:
407:
404:
400:
396:
392:
385:
382:
378:
374:
370:
367:
363:
362:
361:
355:
353:
348:
345:
341:
340:
339:
337:
332:
328:
318:
316:
307:
305:
304:
301:
300:70.249.214.16
297:
293:
286:
283:
279:
260:
254:
251:
248:
242:
236:
227:
226:
225:
223:
219:
207:
206:
201:
197:
194:
191:
187:
186:
170:
166:
160:
157:
156:
152:
146:
143:
142:
139:
122:
118:
114:
113:
105:
99:
94:
92:
89:
85:
84:
80:
71:
68:
65:
61:
56:
52:
46:
38:
37:
27:
23:
18:
17:
660:
640:
596:
591:
589:
584:
581:
577:
574:
570:
566:
562:
558:
554:
550:
546:
543:
539:
536:
529:
525:
521:
517:
513:
509:
505:
502:
501:) steps and
498:
494:
490:
486:
482:
478:
474:
471:
467:
464:
459:
453:
449:
445:
442:
435:
431:
427:
424:
420:
416:
412:
409:
402:
398:
394:
387:
383:
380:
376:
372:
368:
365:
359:
351:
330:
326:
324:
311:
289:
213:
203:
195:
165:Mid-priority
164:
110:
76:Midâpriority
51:WikiProjects
34:
602:Antares5245
593:f(n) steps)
524:is in Time(
448:accept in
441:, and thus
393:, and thus
200:peer review
198:received a
126:Mathematics
117:mathematics
70:Mathematics
41:Start-class
679:Categories
290:How about
644:Taeshadow
334:theorem.
39:is rated
622:Dcoetzee
489:2) not (
205:archived
585:accepts
578:accepts
547:accepts
540:rejects
506:accepts
475:rejects
468:accepts
428:accepts
413:rejects
384:rejects
369:accepts
167:on the
73:Câclass
616:steps.
535:0) If
463:0) If
47:scale.
344:Timwi
282:Timwi
28:This
667:talk
648:talk
606:talk
595:and
561:2) (
446:does
336:Deco
315:here
294:? -
542:1)
470:1)
434:in
408:If
364:If
298:as
249:log
222:Gdr
159:Mid
681::
669:)
650:)
642:--
608:)
432:is
252:âĄ
665:(
646:(
604:(
582:N
575:N
571:n
569:(
567:f
563:N
559:N
555:N
553:,
551:N
549:(
544:K
537:N
530:n
528:(
526:f
522:N
518:n
516:(
514:f
510:N
503:N
499:n
497:(
495:f
491:N
487:N
483:N
481:,
479:N
477:(
472:K
465:N
454:n
452:(
450:f
443:N
438:f
436:H
425:K
421:n
419:(
417:f
410:N
403:n
401:(
399:f
395:N
390:f
388:H
381:K
377:n
375:(
373:f
366:N
331:n
327:n
264:)
261:m
258:(
255:f
246:)
243:m
240:(
237:f
171:.
145:C
53::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
