241:
463:
658:
529:
494:
327:
292:
144:
28:(c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not
607:
580:
112:
627:
553:
391:
371:
351:
261:
188:
168:
787:
193:
760:
726:
396:
814:
79:. They give a construction for a set that is simple (and thus non-computable), but fails to compute the halting problem.
68:. He succeeded in the first part (which is obvious by definition), but for the other part, he managed only to prove a
500:
if it is c.e. and its complement is effectively immune. Every effectively simple set is simple and Turing-complete.
635:
506:
471:
304:
269:
121:
744:
25:
715:
Recursively enumerable sets and degrees. A study of computable functions and computably generated sets
17:
75:
Post's idea was validated by
Friedberg and Muchnik in the 1950s using a novel technique called the
69:
755:. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam: North Holland.
783:
756:
722:
45:
793:
766:
732:
61:
585:
558:
90:
797:
770:
736:
718:
76:
57:
749:
612:
538:
376:
356:
336:
246:
173:
153:
44:
in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as
41:
29:
808:
48:. Post had to prove two things in order to obtain his result: that the simple set
751:
Classical recursion theory. The theory of functions and sets of natural numbers
782:. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press.
236:{\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}
114:
denotes a standard uniformly c.e. listing of all the c.e. sets.
458:{\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}
638:
615:
588:
561:
541:
509:
474:
399:
379:
359:
339:
307:
272:
249:
196:
176:
156:
124:
93:
353:is infinite, but there exists a recursive function
243:. Or equivalently: there is no infinite subset of
748:
664:if it is simple and its complement is hyperimmune.
652:
621:
601:
574:
547:
523:
488:
457:
385:
365:
345:
321:
286:
255:
235:
182:
162:
138:
106:
717:. Perspectives in Mathematical Logic. Berlin:
8:
20:, a subset of the natural numbers is called
298:if it is c.e. and its complement is immune.
420:
416:
216:
212:
646:
645:
637:
614:
593:
587:
566:
560:
540:
517:
516:
508:
482:
481:
473:
431:
404:
398:
378:
358:
338:
315:
314:
306:
280:
279:
271:
248:
221:
207:
201:
195:
175:
155:
132:
131:
123:
98:
92:
674:
653:{\displaystyle S\subseteq \mathbb {N} }
524:{\displaystyle I\subseteq \mathbb {N} }
489:{\displaystyle S\subseteq \mathbb {N} }
322:{\displaystyle I\subseteq \mathbb {N} }
287:{\displaystyle S\subseteq \mathbb {N} }
139:{\displaystyle I\subseteq \mathbb {N} }
83:Formal definitions and some properties
7:
582:is not computably dominated, where
421:
14:
170:is infinite, but for every index
52:is not computable, and that the
452:
446:
437:
424:
417:
213:
1:
780:Computability and randomness
40:Simple sets were devised by
831:
609:is the list of members of
373:such that for every index
36:Relation to Post's problem
713:Soare, Robert I. (1987).
35:
745:Odifreddi, Piergiorgio
654:
623:
603:
576:
549:
525:
490:
459:
387:
367:
347:
323:
288:
257:
237:
184:
164:
140:
108:
655:
624:
604:
602:{\displaystyle p_{I}}
577:
575:{\displaystyle p_{I}}
550:
526:
491:
460:
388:
368:
348:
324:
289:
258:
238:
185:
165:
141:
109:
107:{\displaystyle W_{e}}
26:computably enumerable
815:Computability theory
778:Nies, André (2009).
636:
613:
586:
559:
539:
507:
472:
397:
377:
357:
337:
305:
270:
247:
194:
174:
154:
122:
91:
18:computability theory
650:
619:
599:
572:
545:
521:
498:effectively simple
486:
455:
383:
363:
343:
331:effectively immune
319:
284:
253:
233:
180:
160:
136:
104:
70:many-one reduction
789:978-0-19-923076-1
622:{\displaystyle I}
555:is infinite, but
548:{\displaystyle I}
386:{\displaystyle e}
366:{\displaystyle f}
346:{\displaystyle I}
256:{\displaystyle I}
210:
183:{\displaystyle e}
163:{\displaystyle I}
87:In what follows,
822:
801:
774:
754:
740:
700:
699:Nies (2009) p.37
697:
691:
690:Nies (2009) p.27
688:
682:
681:Nies (2009) p.35
679:
659:
657:
656:
651:
649:
628:
626:
625:
620:
608:
606:
605:
600:
598:
597:
581:
579:
578:
573:
571:
570:
554:
552:
551:
546:
530:
528:
527:
522:
520:
495:
493:
492:
487:
485:
464:
462:
461:
456:
436:
435:
409:
408:
392:
390:
389:
384:
372:
370:
369:
364:
352:
350:
349:
344:
328:
326:
325:
320:
318:
293:
291:
290:
285:
283:
262:
260:
259:
254:
242:
240:
239:
234:
226:
225:
211:
208:
206:
205:
189:
187:
186:
181:
169:
167:
166:
161:
145:
143:
142:
137:
135:
113:
111:
110:
105:
103:
102:
830:
829:
825:
824:
823:
821:
820:
819:
805:
804:
790:
777:
763:
743:
729:
719:Springer-Verlag
712:
709:
704:
703:
698:
694:
689:
685:
680:
676:
671:
634:
633:
611:
610:
589:
584:
583:
562:
557:
556:
537:
536:
505:
504:
470:
469:
427:
400:
395:
394:
393:, we have that
375:
374:
355:
354:
335:
334:
303:
302:
268:
267:
245:
244:
217:
197:
192:
191:
172:
171:
152:
151:
120:
119:
94:
89:
88:
85:
77:priority method
58:halting problem
38:
12:
11:
5:
828:
826:
818:
817:
807:
806:
803:
802:
788:
775:
761:
741:
727:
708:
705:
702:
701:
692:
683:
673:
672:
670:
667:
666:
665:
648:
644:
641:
630:
618:
596:
592:
569:
565:
544:
519:
515:
512:
501:
484:
480:
477:
466:
454:
451:
448:
445:
442:
439:
434:
430:
426:
423:
419:
415:
412:
407:
403:
382:
362:
342:
317:
313:
310:
299:
282:
278:
275:
264:
252:
232:
229:
224:
220:
215:
209: infinite
204:
200:
179:
159:
134:
130:
127:
101:
97:
84:
81:
46:Post's problem
42:Emil Leon Post
37:
34:
13:
10:
9:
6:
4:
3:
2:
827:
816:
813:
812:
810:
799:
795:
791:
785:
781:
776:
772:
768:
764:
762:0-444-87295-7
758:
753:
752:
746:
742:
738:
734:
730:
728:3-540-15299-7
724:
720:
716:
711:
710:
706:
696:
693:
687:
684:
678:
675:
668:
663:
642:
639:
631:
616:
594:
590:
567:
563:
542:
534:
513:
510:
502:
499:
478:
475:
467:
449:
443:
440:
432:
428:
413:
410:
405:
401:
380:
360:
340:
332:
311:
308:
300:
297:
276:
273:
265:
263:that is c.e..
250:
230:
227:
222:
218:
202:
198:
177:
157:
149:
128:
125:
117:
116:
115:
99:
95:
82:
80:
78:
73:
71:
67:
63:
62:Turing-reduce
59:
55:
51:
47:
43:
33:
31:
27:
23:
19:
779:
750:
714:
695:
686:
677:
661:
532:
497:
330:
295:
147:
86:
74:
65:
53:
49:
39:
21:
15:
662:hypersimple
533:hyperimmune
60:, does not
798:1169.03034
771:0661.03029
737:0667.03030
707:References
660:is called
531:is called
496:is called
329:is called
190:, we have
146:is called
30:computable
643:⊆
629:in order.
514:⊆
479:⊆
422:#
418:⟹
411:⊆
312:⊆
294:is called
277:⊆
214:⟹
129:⊆
24:if it is
809:Category
747:(1988).
228:⊈
296:simple
796:
786:
769:
759:
735:
725:
632:A set
503:A set
468:A set
301:A set
266:A set
148:immune
118:A set
56:, the
22:simple
669:Notes
784:ISBN
757:ISBN
723:ISBN
441:<
794:Zbl
767:Zbl
733:Zbl
535:if
333:if
150:if
64:to
16:In
811::
792:.
765:.
731:.
721:.
72:.
32:.
800:.
773:.
739:.
647:N
640:S
617:I
595:I
591:p
568:I
564:p
543:I
518:N
511:I
483:N
476:S
465:.
453:)
450:e
447:(
444:f
438:)
433:e
429:W
425:(
414:I
406:e
402:W
381:e
361:f
341:I
316:N
309:I
281:N
274:S
251:I
231:I
223:e
219:W
203:e
199:W
178:e
158:I
133:N
126:I
100:e
96:W
66:A
54:K
50:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.