498:
106:
96:
75:
42:
1058:(bounded) distributive lattice. These are fun facts, but I don't know if they are of any use at all (I am by no means an expert in computability theory). If these facts are useful then I suggest that they be added to this article as well the article 'recursively enumerable set', and even if they are totally useless, perhaps they are interesting enough to be included anyway. Let me know what you think.
33:
843:
To
Vladimir: Thanks. It would be nice to find a restriction which would allow us to include this extension. Essentially the Gödel numbering itself needs to be recursive or, better, primitive recursive. Notice that the generalized notion of recursive must be closed under composition, and the same as
870:
What would it mean for an algorithm on an arbitrary countable set to be recursive? I don't see a general definition of that which does not assume the prior existence of a numbering. It could be defined on a case by case basis for many of the countable sets which we encounter in practice, because
1057:
Because the empty set and the set of natural numbers are recursive sets, and because recursive sets are closed under intersections, unions, and complements, they form a boolean algebra. Computably enumerable sets are closed under intersections and unions but not under complements and thus form a
470:
My reasons are quite independent of the current state of the article. The fact is that r.e. sets can be significantly more complex than recursive ones, and there's quite a lot to say about them. Since this proposal has attracted no support in more than five months, I'm removing the template.
732:
a paragraph saying that Gödel numbers can be used to extend the definition of recursive to sets which are not subsets of the natural numbers. If no restriction is imposed on how the Gödel numbers are formed, this is false and would make every countable set recursive. Suppose
426:
For anyone keeping this article on their watchlist: there is currently an attempt at merging a number of articles on (non-)recursive/(un)decidable/(un)computable sets/languages/decision problems into a single, thorough article. The experiment currently sits at
888:
One other way is to use the
Weirauch-style definitions. Unfortunately we don't seem to have any article on what they call type two computability. The idea is that the numbering is just an arbitrary partial sujection from
798:
Yes, I think you did the right thing. I think I understand
Vladimir's point — it's not uncommon to speak of recursive or r.e. sets of this or that sort of thing other than natural numbers, when the things are naturally
238:
of the arithmetical hierarchy. That means it is definable by a formula beginning with an unbounded quantifier and using only bounded quantifiers thereafter. This doesn't seem too likely. For instance, one
974:). The function δ is just a function, it has no effectiveness requirements. So the definition of δ-computability does depend on δ, but one nice aspect of it is that the definition is quite general. — Carl
803:
as natural numbers. But I don't know that there's a way generalize this observation and put it into the articles, without running into the problem you identify. In any case it would need a source. --
162:
940:
1117:
271:
set is the set of numbers which are bounded above by a twin prime, which is not known to be recursive AFAIK. I certainly can't think of a good algorithm for determining that :-)
375:
343:
269:
236:
909:
311:
1122:
1107:
46:
1112:
1132:
665:
152:
614:
for sure. But I should mention, that there is a bijection between these sets and natural numbers. On the right, you see the first sixteen sets between
1127:
1102:
725:
128:
672:
The diagram at the top of the page is misleading: decidable sets are a subset of recursively enumerable sets, but not of undecidable sets.
1007:
To CBM: Are you saying that we could have a notion of recursive relative to an oracle with the Gödel numbering provided by the oracle? See
1097:
679:
119:
80:
821:
Indeed, without restrictions on encoding it can lead to a wrong conclusion. I will look for sources explaining how to handle this.
826:
719:
693:
You are right; the diagram should be different. I moved it here so people can still see what you are referring to. — Carl
55:
557:
450:
428:
914:
1011:. Although that is still limited to subsets of the natural numbers, perhaps one could encode some sets (beyond
822:
715:
497:
401:
Therefore (proof by cases) this is a recursive set, although it isn't known which of these sets it is. — Carl
32:
683:
1063:
1026:
390:
You are confused about something. The "set of numbers which are bounded above by a twin prime" is either:
61:
1059:
737:
is any countably infinite set (of course all finite sets are recursive) and in particular the function
105:
642:}}}} = 16, and so on. Maybe it's helpful to know that, to decide if they are both pure and recursive.
675:
664:
348:
316:
242:
209:
1078:
1034:
1025:
I was thinking more along the lines of trying to extend the domain from the natural numbers to the
849:
808:
788:
647:
597:
578:
476:
458:
193:
127:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
892:
538:
436:
284:
111:
95:
74:
549:
962:. A function $ g$ is δ-computable if there is an algorithm that, given a name for an element
1019:
781:(all the natural numbers), and thus would be recursive by this extension of the definition.
396:
or a set of the form {0,1,2,...,p,p+1} where p and p+2 are the largest pair of twin primes.
783:
Since this extension of the definition would reduce it to a triviality, I will revert it.
1074:
1030:
1008:
845:
804:
784:
643:
593:
574:
472:
454:
185:
1091:
981:
729:
700:
564:
502:
432:
408:
189:
17:
453:. I do not want it to be destroyed by merging it into another, inferior article.
124:
378:
272:
101:
639:
635:
631:
627:
623:
619:
615:
534:
530:
526:
522:
518:
514:
510:
491:
487:
393:
The entire set of natural numbers, if there are infinitely many twin primes
977:
696:
668:
Diagram showing the closure of decision problems in computational theory.
611:
589:
404:
1082:
1067:
1038:
986:
853:
830:
812:
792:
705:
687:
651:
601:
582:
480:
462:
440:
413:
381:
275:
206:
The article says that a set is recursive if and only if it is at level
196:
663:
553:
281:
Pardon me, I have made an error. My twin primes statement is
26:
1073:
Sounds like a good idea to me, if you include a reference.
777:
is the subset of itself corresponding to the recursive set
568:(hard to read, but equal to my Hasse diagram on the right)
844:
the usual notion when restricted to the natural numbers.
192:. Are there any objections if I reverse that redirect?
542:
917:
895:
351:
319:
287:
245:
212:
570:
he calls this "recursive sets". Does it make sense?
123:, a collaborative effort to improve the coverage of
934:
903:
369:
337:
305:
263:
230:
1118:Knowledge level-5 vital articles in Mathematics
741:is a bijection between the natural numbers and
8:
588:I think he is confusing recursive sets with
935:{\displaystyle \mathbb {N} ^{\mathbb {N} }}
30:
69:
1123:Start-Class vital articles in Mathematics
926:
925:
924:
920:
919:
916:
897:
896:
894:
449:A lot of effort has gone into perfecting
361:
356:
350:
329:
324:
318:
297:
292:
286:
255:
250:
244:
222:
217:
211:
496:
1108:Knowledge vital articles in Mathematics
548:Originally this came from Commons user
501:Are these "recursive sets", as claimed
71:
509:Hi. Some time ago the interesting set
1029:or perhaps just the ordinal numbers.
871:they have nice numberings, of course.
753:, let us declare the Gödel number of
638:}} } = 15. The next set would be {{{{
7:
556:. Where ever he's got this from, he
117:This article is within the scope of
60:It is of interest to the following
1113:Start-Class level-5 vital articles
1018:) as natural numbers. Maybe using
563:In the description of his diagram
353:
321:
289:
247:
214:
25:
1133:Mid-priority mathematics articles
1053:Boolean algebra of recursive sets
137:Knowledge:WikiProject Mathematics
1128:Start-Class mathematics articles
1103:Knowledge level-5 vital articles
140:Template:WikiProject Mathematics
104:
94:
73:
40:
31:
730:Recursive set#Formal definition
370:{\displaystyle \Delta _{1}^{0}}
338:{\displaystyle \Sigma _{1}^{0}}
264:{\displaystyle \Delta _{1}^{0}}
231:{\displaystyle \Delta _{1}^{0}}
157:This article has been rated as
1:
1039:11:04, 15 December 2011 (UTC)
987:12:47, 14 December 2011 (UTC)
854:06:43, 14 December 2011 (UTC)
831:19:45, 12 December 2011 (UTC)
813:21:18, 11 December 2011 (UTC)
793:21:00, 11 December 2011 (UTC)
441:00:42, 21 February 2008 (UTC)
431:. Comments are very welcome.
131:and see a list of open tasks.
904:{\displaystyle \mathbb {N} }
706:18:53, 9 November 2009 (UTC)
688:18:38, 9 November 2009 (UTC)
429:Recursive languages and sets
306:{\displaystyle \Pi _{1}^{0}}
1149:
1098:Start-Class vital articles
537:)))) has been used in the
481:02:38, 9 August 2008 (UTC)
468:Oppose and remove template
451:Recursively enumerable set
757:to be the natural number
652:11:01, 13 June 2009 (UTC)
602:21:08, 12 June 2009 (UTC)
583:13:17, 12 June 2009 (UTC)
197:23:35, 16 July 2006 (UTC)
156:
89:
68:
1083:09:09, 17 May 2019 (UTC)
1068:20:50, 16 May 2019 (UTC)
463:01:33, 27 May 2008 (UTC)
414:13:05, 8 July 2007 (UTC)
382:11:54, 8 July 2007 (UTC)
276:11:49, 8 July 2007 (UTC)
163:project's priority scale
120:WikiProject Mathematics
966:, produces a name for
936:
905:
669:
610:Possibly, as they are
506:
371:
339:
307:
265:
232:
937:
906:
728:) has twice added to
667:
500:
372:
340:
308:
266:
233:
47:level-5 vital article
915:
893:
349:
317:
285:
243:
210:
143:mathematics articles
823:VladimirReshetnikov
745:. For each element
716:VladimirReshetnikov
539:logical connectives
366:
334:
302:
260:
227:
1027:constructible sets
932:
901:
670:
660:Diagram Misleading
507:
367:
352:
335:
320:
303:
288:
261:
246:
228:
213:
112:Mathematics portal
56:content assessment
18:Talk:Recursive set
985:
704:
678:comment added by
569:
541:article, but was
412:
313:but probably not
177:
176:
173:
172:
169:
168:
16:(Redirected from
1140:
1020:infinitary logic
975:
958:is a "name" for
941:
939:
938:
933:
931:
930:
929:
923:
910:
908:
907:
902:
900:
694:
690:
567:
558:doesn't remember
422:attempt to merge
402:
376:
374:
373:
368:
365:
360:
344:
342:
341:
336:
333:
328:
312:
310:
309:
304:
301:
296:
270:
268:
267:
262:
259:
254:
237:
235:
234:
229:
226:
221:
180:Reverse redirect
145:
144:
141:
138:
135:
114:
109:
108:
98:
91:
90:
85:
77:
70:
53:
44:
43:
36:
35:
27:
21:
1148:
1147:
1143:
1142:
1141:
1139:
1138:
1137:
1088:
1087:
1055:
1017:
918:
913:
912:
891:
890:
713:
673:
662:
495:
424:
347:
346:
315:
314:
283:
282:
241:
240:
208:
207:
204:
202:Hierarchy error
182:
142:
139:
136:
133:
132:
110:
103:
83:
54:on Knowledge's
51:
41:
23:
22:
15:
12:
11:
5:
1146:
1144:
1136:
1135:
1130:
1125:
1120:
1115:
1110:
1105:
1100:
1090:
1089:
1086:
1085:
1054:
1051:
1050:
1049:
1048:
1047:
1046:
1045:
1044:
1043:
1042:
1041:
1023:
1015:
1009:Oracle machine
996:
995:
994:
993:
992:
991:
990:
989:
928:
922:
899:
879:
878:
877:
876:
875:
874:
873:
872:
861:
860:
859:
858:
857:
856:
836:
835:
834:
833:
816:
815:
782:
712:
709:
661:
658:
657:
656:
655:
654:
605:
604:
494:
485:
484:
483:
465:
423:
420:
419:
418:
417:
416:
399:
398:
397:
394:
385:
384:
364:
359:
355:
345:, so it's not
332:
327:
323:
300:
295:
291:
258:
253:
249:
225:
220:
216:
203:
200:
186:Computable set
181:
178:
175:
174:
171:
170:
167:
166:
155:
149:
148:
146:
129:the discussion
116:
115:
99:
87:
86:
78:
66:
65:
59:
37:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1145:
1134:
1131:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1109:
1106:
1104:
1101:
1099:
1096:
1095:
1093:
1084:
1080:
1076:
1072:
1071:
1070:
1069:
1065:
1061:
1052:
1040:
1036:
1032:
1028:
1024:
1021:
1014:
1010:
1006:
1005:
1004:
1003:
1002:
1001:
1000:
999:
998:
997:
988:
983:
979:
973:
969:
965:
961:
957:
953:
949:
945:
887:
886:
885:
884:
883:
882:
881:
880:
869:
868:
867:
866:
865:
864:
863:
862:
855:
851:
847:
842:
841:
840:
839:
838:
837:
832:
828:
824:
820:
819:
818:
817:
814:
810:
806:
802:
797:
796:
795:
794:
790:
786:
780:
776:
772:
768:
764:
760:
756:
752:
748:
744:
740:
736:
731:
727:
724:
721:
717:
711:Gödel numbers
710:
708:
707:
702:
698:
691:
689:
685:
681:
677:
666:
659:
653:
649:
645:
641:
637:
633:
629:
625:
621:
617:
613:
609:
608:
607:
606:
603:
599:
595:
591:
587:
586:
585:
584:
580:
576:
571:
566:
565:File:Set0.gif
561:
559:
555:
551:
546:
544:
540:
536:
532:
528:
524:
520:
516:
512:
504:
499:
493:
489:
486:
482:
478:
474:
469:
466:
464:
460:
456:
452:
448:
447:Oppose merger
445:
444:
443:
442:
438:
434:
430:
421:
415:
410:
406:
400:
395:
392:
391:
389:
388:
387:
386:
383:
380:
362:
357:
330:
325:
298:
293:
280:
279:
278:
277:
274:
256:
251:
223:
218:
201:
199:
198:
195:
191:
190:recursive set
188:redirects to
187:
179:
164:
160:
154:
151:
150:
147:
130:
126:
122:
121:
113:
107:
102:
100:
97:
93:
92:
88:
82:
79:
76:
72:
67:
63:
57:
49:
48:
38:
34:
29:
28:
19:
1060:Joel Brennan
1056:
1012:
971:
967:
963:
959:
955:
951:
947:
943:
800:
778:
774:
770:
766:
762:
758:
754:
750:
746:
742:
738:
734:
722:
714:
692:
680:78.131.31.31
671:
572:
562:
554:his homepage
547:
508:
467:
446:
425:
205:
183:
159:Mid-priority
158:
118:
84:Mid‑priority
62:WikiProjects
45:
942:to the set
674:—Preceding
184:Right now,
134:Mathematics
125:mathematics
81:Mathematics
52:Start-class
1092:Categories
761:such that
618:= 0 and {
488:Power sets
1075:JRSpriggs
1031:JRSpriggs
846:JRSpriggs
805:Trovatore
785:JRSpriggs
644:Watchduck
594:JRSpriggs
590:pure sets
575:Watchduck
550:Dohduhdah
492:empty set
473:Trovatore
455:JRSpriggs
50:is rated
726:contribs
676:unsigned
573:Thanks,
433:Pichpich
194:CMummert
946:; if δ(
773:. Then
543:removed
490:of the
161:on the
630:}} , {
58:scale.
954:then
801:coded
626:}, {{
379:Luqui
273:Luqui
39:This
1079:talk
1064:talk
1035:talk
982:talk
950:) =
850:talk
827:talk
809:talk
789:talk
720:talk
701:talk
684:talk
648:talk
612:pure
598:talk
579:talk
552:and
517:) =
503:here
477:talk
459:talk
437:talk
409:talk
978:CBM
911:or
749:of
697:CBM
622:, {
545:.
513:^4(
405:CBM
153:Mid
1094::
1081:)
1066:)
1037:)
980:·
852:)
829:)
811:)
791:)
769:)=
699:·
686:)
650:)
640:{}
636:{}
634:,{
632:{}
628:{}
624:{}
620:{}
616:{}
600:)
592:.
581:)
560:.
535:{}
525:(
521:(
515:{}
479:)
471:--
461:)
439:)
407:·
377:.
354:Δ
322:Σ
290:Π
248:Δ
215:Δ
1077:(
1062:(
1033:(
1022:?
1016:ω
1013:V
984:)
976:(
972:y
970:(
968:g
964:y
960:y
956:z
952:y
948:z
944:X
927:N
921:N
898:N
848:(
825:(
807:(
787:(
779:N
775:A
771:a
767:n
765:(
763:f
759:n
755:a
751:A
747:a
743:A
739:f
735:A
723:·
718:(
703:)
695:(
682:(
646:(
596:(
577:(
533:(
531:P
529:(
527:P
523:P
519:P
511:P
505:?
475:(
457:(
435:(
411:)
403:(
363:0
358:1
331:0
326:1
299:0
294:1
257:0
252:1
224:0
219:1
165:.
64::
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
