413:
Clearly, this machine will never halt. But according to the Zeno machines enthusiasts, if you take the accelerated version of this machine, then it should stop after some finite amount of time, having taken infinitely many steps. Indeed, all Zeno machines should halt according to their specifications. Personally, that sounds baloney to me. By definition of infinity, taking infinitely many steps means that you will never finish going through those steps, whether you accelerate this or not. Indeed, I would say we have reached a logical contradiction here, just as in Zeno's paradox. Therefore, I declare Zeno machines to be logically impossible (note: not just physically impossible, but
151:
74:
53:
22:
523:
undefined. We only get an output if the first cell stabilises (e.g. the machine keeps writing ones in the first cell from some point). So I think what here is meant by "The halting problem for Zeno machines" is this: Given a Zeno machine Z and input i, does Z with input i give an output? Hope that helps somebody.
568:
The halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. It is suggested that claims to have “broken the Turing barrier” could be toned down and that the important and well-founded rôle of
494:
OK, so what are you saying?!? You seem to be contradicting yourself. Anyway, in the end you apparently agree that, if the concept of a Zeno machine holds any water, all Zeno machines should halt. But clearly that leads to trouble, as the examples given earlier demonstrate. Pure logic thus derives a
451:
Well, that is _one_ answer, depending on how you define division and infinity. Under the simplest definitions, any positive number n, finite or infinite, satisfies the equation n x infinity = infinity. So infinity is a valid answer, but so is 1, or 23.42. So, looked at it that way, the answer isn't
461:
But really, there is an answer. The problem doesn't come down to "what's infinity over infinity." The rate of acceleration is proportional to the number of steps. If it takes x steps to halt, it takes 1-1/2^x minutes to halt. The limit of this time as x approaches infinity is 1. So, a Zeno machine
412:
If you accept the logical possibility of Zeno machines, that would seem to be the logical conclusion, yes. But as noted in the article, accepting the possibility of Zeno machines leads to some serious problems: take the turing machine that simply keeps moving left, no matter what symbol it reads.
629:
I suspect it depends on how many limit ordinals the Zeno machine is allowed to reach. If the next limit ordinal is one we’ve decided should be forbidden, then we will just treat it like an ordinary Turing machine from then on (either it halts or it runs forever). Otherwise we let it reset itself
522:
Think about it this way: We want to read the output of computation from the tape. Suppose we read it from the first cell. In one computation a Zeno machine can write to the cell infinitely many times (e.g. zero and one alternatively). What is the output after computation is "finished"? It may
172:
565:
This paper reviews the Church–Turing Thesis (or rather, theses) with reference to their origin and application and considers some models of “hypercomputation”, concentrating on perhaps the most straight-forward option: Zeno machines (Turing machines with accelerating clock).
657:
This means that the Zeno machine can keep getting more and more powerful (in terms of Turing jumps), depending on how many limit ordinals it is allowed to access. If you wanted to, you could even let it cross over to ω·ω, by taking the
635:
If it is designed to only “cross infinity” once, it will have the same power as a TM with an TM Oracle. If it can do so twice (i.e, it can reach step ω·2, but not ω·3), it would have the same power as a TM augmented with
471:
That doesn't prove that a Zeno machine is logically possible--just that any Zeno machines that are logically possible (of which there might be none) halt. That's enough to make the halting functional trivial.
495:
contradiction from the possibility of Zeno machines. In other words, Zeno machines are impossible. And no assumptions about infinity / infinity need to be made in order to derive that contradiction.
595:; if it can do step number \omega, \omega+1, ..., then the halting question seems like it's probably sensible. Maybe someone can check the source and update the main article with a clarification.
196:
336:
253:
191:
714:
124:
114:
666:
states it attained at each ω·n (when n was finite). It at least makes sense logically even if it’s hard to visualize (and impossible for a physical machine to do).
719:
709:
614:
A ZM can solve the TM-halting problem. So can a TM-Oracle, by definition. Does a ZM have equivalent computational power to a TM augmented with a TM-Oracle?
686:
A Zeno machine can solve the halting problem for a Turing machine. What can solve the halting problem for a Zeno machine? -32ieww 10:04PM 11/20/2015 NY time
90:
298:
272:
137:
81:
58:
361:
577:
548:
402:
Is this true? Don't all Zeno machines halt, making the halting function trivially f(T, i) = 1 for any Zeno machine T with any input i? --
502:
473:
424:
244:
225:
317:
282:
163:
33:
292:
206:
442:
Except that the Zeno machine accelerates infinitely. So you're insisting that infinity / infinity = infinity. Nope.
327:
89:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
591:
I haven't read the paper, but my guess would be that a ZM is allowed to do \omega steps of computation, and then
354:
649:
581:
552:
21:
506:
428:
671:
528:
477:
263:
39:
573:
544:
498:
420:
615:
596:
619:
600:
667:
524:
182:
691:
234:
86:
538:"(The halting problem for Zeno machines cannot be solved using a Zeno machine, however)."
399:"(The halting problem for Zeno machines cannot be solved using a Zeno machine, however)."
308:
150:
173:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
703:
541:
of course its true it says on the paper. have you actually read the paper you cite?
403:
687:
645:
215:
73:
52:
452:"no"--there's not enough information in the problem to provide an answer.
569:
Turing computability in the mathematical sciences stands unchallenged.
695:
675:
623:
604:
585:
556:
532:
510:
481:
432:
406:
291:
Find pictures for the biographies of computer scientists (see
15:
85:, a collaborative effort to improve the coverage of
197:Computer science articles needing expert attention
337:WikiProject Computer science/Unreferenced BLPs
8:
644:. Thus it would be even more powerful. See
254:Computer science articles without infoboxes
192:Computer science articles needing attention
19:
648:, which is a closely related topic, as is
158:Here are some tasks awaiting attention:
132:
47:
630:(with lim sup) at the next limit ordinal.
715:Low-importance Computer science articles
49:
99:Knowledge:WikiProject Computer science
720:WikiProject Computer science articles
710:Start-Class Computer science articles
102:Template:WikiProject Computer science
7:
79:This article is within the scope of
38:It is of interest to the following
273:Timeline of computing 2020–present
14:
299:Computing articles needing images
149:
72:
51:
20:
119:This article has been rated as
1:
696:03:04, 21 November 2015 (UTC)
533:13:44, 29 November 2010 (UTC)
482:16:52, 16 February 2009 (UTC)
353:Tag all relevant articles in
93:and see a list of open tasks.
638:an oracle for TM’s that are
586:08:45, 6 November 2009 (UTC)
557:08:40, 6 November 2009 (UTC)
362:WikiProject Computer science
138:WikiProject Computer science
82:WikiProject Computer science
293:List of computer scientists
736:
676:04:27, 29 March 2024 (UTC)
624:19:40, 6 August 2012 (UTC)
605:19:30, 6 August 2012 (UTC)
511:21:16, 15 March 2009 (UTC)
407:01:06, 20 March 2006 (UTC)
125:project's importance scale
642:augmented with TM oracles
355:Category:Computer science
131:
118:
105:Computer science articles
67:
46:
650:hyperarithmetical theory
433:20:07, 3 July 2008 (UTC)
357:and sub-categories with
682:What is the next step?
318:Computer science stubs
28:This article is rated
136:Things you can help
610:Computational power
34:content assessment
576:comment added by
547:comment added by
501:comment added by
435:
423:comment added by
392:
391:
388:
387:
384:
383:
380:
379:
376:
375:
727:
588:
559:
513:
418:
366:
360:
235:Computer science
164:Article requests
153:
146:
145:
133:
107:
106:
103:
100:
97:
96:Computer science
87:Computer science
76:
69:
68:
63:
59:Computer science
55:
48:
31:
25:
24:
16:
735:
734:
730:
729:
728:
726:
725:
724:
700:
699:
684:
612:
571:
542:
496:
397:
395:Halting Problem
372:
369:
364:
358:
346:Project-related
341:
322:
303:
277:
258:
239:
220:
201:
177:
104:
101:
98:
95:
94:
61:
32:on Knowledge's
29:
12:
11:
5:
733:
731:
723:
722:
717:
712:
702:
701:
683:
680:
679:
678:
654:
653:
632:
631:
611:
608:
578:138.250.193.98
549:138.250.193.98
536:
535:
519:
518:
517:
516:
515:
514:
487:
486:
485:
484:
466:
465:
464:
463:
456:
455:
454:
453:
446:
445:
444:
443:
437:
436:
417:impossible).
396:
393:
390:
389:
386:
385:
382:
381:
378:
377:
374:
373:
371:
370:
368:
367:
350:
342:
340:
339:
333:
323:
321:
320:
314:
304:
302:
301:
296:
288:
278:
276:
275:
269:
259:
257:
256:
250:
240:
238:
237:
231:
221:
219:
218:
212:
202:
200:
199:
194:
188:
178:
176:
175:
169:
157:
155:
154:
142:
141:
129:
128:
121:Low-importance
117:
111:
110:
108:
91:the discussion
77:
65:
64:
62:Low‑importance
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
732:
721:
718:
716:
713:
711:
708:
707:
705:
698:
697:
693:
689:
681:
677:
673:
669:
668:LonelyBoy2012
665:
661:
656:
655:
651:
647:
643:
641:
634:
633:
628:
627:
626:
625:
621:
617:
609:
607:
606:
602:
598:
594:
589:
587:
583:
579:
575:
570:
563:
560:
558:
554:
550:
546:
539:
534:
530:
526:
525:Czego szukasz
521:
520:
512:
508:
504:
503:67.244.167.93
500:
493:
492:
491:
490:
489:
488:
483:
479:
475:
474:75.36.137.180
470:
469:
468:
467:
462:always halts.
460:
459:
458:
457:
450:
449:
448:
447:
441:
440:
439:
438:
434:
430:
426:
425:72.226.66.230
422:
416:
411:
410:
409:
408:
405:
400:
394:
363:
356:
352:
351:
349:
347:
343:
338:
335:
334:
332:
330:
329:
324:
319:
316:
315:
313:
311:
310:
305:
300:
297:
294:
290:
289:
287:
285:
284:
279:
274:
271:
270:
268:
266:
265:
260:
255:
252:
251:
249:
247:
246:
241:
236:
233:
232:
230:
228:
227:
222:
217:
214:
213:
211:
209:
208:
203:
198:
195:
193:
190:
189:
187:
185:
184:
179:
174:
171:
170:
168:
166:
165:
160:
159:
156:
152:
148:
147:
144:
143:
139:
135:
134:
130:
126:
122:
116:
113:
112:
109:
92:
88:
84:
83:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
685:
663:
659:
639:
637:
613:
592:
590:
567:
564:
561:
540:
537:
414:
401:
398:
345:
344:
328:Unreferenced
326:
325:
307:
306:
281:
280:
262:
261:
243:
242:
224:
223:
205:
204:
181:
180:
162:
161:
120:
80:
40:WikiProjects
646:Turing jump
572:—Preceding
543:—Preceding
497:—Preceding
419:—Preceding
30:Start-class
704:Categories
640:themselves
593:keep going
616:Joule36e5
597:Joule36e5
562:Abstract
415:logically
216:Computing
574:unsigned
545:unsigned
499:unsigned
421:unsigned
264:Maintain
207:Copyedit
664:lim sup
662:of the
660:lim sup
404:NoizHed
245:Infobox
183:Cleanup
123:on the
688:32ieww
226:Expand
36:scale.
309:Stubs
283:Photo
140:with:
692:talk
672:talk
620:talk
601:talk
582:talk
553:talk
529:talk
507:talk
478:talk
429:talk
115:Low
706::
694:)
674:)
622:)
603:)
584:)
555:)
531:)
509:)
480:)
472:--
431:)
365:}}
359:{{
690:(
670:(
652:.
618:(
599:(
580:(
551:(
527:(
505:(
476:(
427:(
348::
331::
312::
295:)
286::
267::
248::
229::
210::
186::
167::
127:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
