459:
103:
179:
151:
316:
214:
260:
240:
443:
44:
284:
123:
524:
500:
17:
436:
529:
374:
220:
519:
429:
72:
493:
409:
327:
156:
128:
486:
289:
362:
466:
331:
370:
470:
413:
184:
384:
380:
245:
225:
23:
269:
108:
59:
47:
513:
318:. Computably isomorphic numberings induce the same notion of computability on a set.
330:, the relation of computable isomorphism coincides with the relation of mutual
62:
66:
458:
367:
Theory of recursive functions and effective computability
352:
Theory of recursive functions and effective computability
474:
417:
292:
272:
248:
228:
187:
159:
131:
111:
75:
26:
98:{\displaystyle f\colon \mathbb {N} \to \mathbb {N} }
310:
278:
254:
234:
208:
173:
145:
117:
97:
38:
494:
437:
8:
501:
487:
444:
430:
369:(2nd ed.), Cambridge, MA: MIT Press,
291:
271:
247:
227:
186:
167:
166:
158:
139:
138:
130:
110:
91:
90:
83:
82:
74:
25:
343:
266:if there exists a computable bijection
174:{\displaystyle B\subseteq \mathbb {N} }
146:{\displaystyle A\subseteq \mathbb {N} }
7:
455:
453:
397:
395:
350:Theorem 7.VI, Hartley Rogers, Jr.,
525:Theoretical computer science stubs
473:. You can help Knowledge (XXG) by
416:. You can help Knowledge (XXG) by
14:
457:
311:{\displaystyle \nu =\mu \circ f}
197:
191:
87:
1:
410:theoretical computer science
546:
452:
394:
328:Myhill isomorphism theorem
530:Mathematical logic stubs
105:such that the image of
520:Reduction (complexity)
469:-related article is a
412:–related article is a
312:
280:
256:
236:
210:
209:{\displaystyle f(A)=B}
175:
147:
119:
99:
56:recursively isomorphic
40:
313:
281:
264:computably isomorphic
257:
237:
211:
176:
148:
120:
100:
52:computably isomorphic
41:
332:one-one reducibility
290:
270:
255:{\displaystyle \mu }
246:
235:{\displaystyle \nu }
226:
185:
157:
129:
109:
73:
24:
18:computability theory
363:Rogers, Hartley Jr.
39:{\displaystyle A,B}
467:mathematical logic
308:
276:
252:
232:
206:
171:
143:
115:
95:
58:if there exists a
36:
482:
481:
425:
424:
279:{\displaystyle f}
118:{\displaystyle f}
537:
503:
496:
489:
461:
454:
446:
439:
432:
401:P ≟ NP
396:
387:
354:
348:
317:
315:
314:
309:
285:
283:
282:
277:
261:
259:
258:
253:
241:
239:
238:
233:
215:
213:
212:
207:
180:
178:
177:
172:
170:
152:
150:
149:
144:
142:
124:
122:
121:
116:
104:
102:
101:
96:
94:
86:
45:
43:
42:
37:
545:
544:
540:
539:
538:
536:
535:
534:
510:
509:
508:
507:
451:
450:
403:
392:
377:
361:
358:
357:
349:
345:
340:
324:
288:
287:
268:
267:
244:
243:
224:
223:
183:
182:
155:
154:
127:
126:
107:
106:
71:
70:
48:natural numbers
22:
21:
12:
11:
5:
543:
541:
533:
532:
527:
522:
512:
511:
506:
505:
498:
491:
483:
480:
479:
462:
449:
448:
441:
434:
426:
423:
422:
405:
399:
390:
389:
375:
356:
355:
342:
341:
339:
336:
323:
320:
307:
304:
301:
298:
295:
275:
251:
231:
205:
202:
199:
196:
193:
190:
169:
165:
162:
141:
137:
134:
125:restricted to
114:
93:
89:
85:
81:
78:
35:
32:
29:
13:
10:
9:
6:
4:
3:
2:
542:
531:
528:
526:
523:
521:
518:
517:
515:
504:
499:
497:
492:
490:
485:
484:
478:
476:
472:
468:
463:
460:
456:
447:
442:
440:
435:
433:
428:
427:
421:
419:
415:
411:
406:
402:
398:
393:
386:
382:
378:
376:0-262-68052-1
372:
368:
364:
360:
359:
353:
347:
344:
337:
335:
333:
329:
321:
319:
305:
302:
299:
296:
293:
273:
265:
249:
229:
222:
219:Further, two
217:
203:
200:
194:
188:
163:
160:
135:
132:
112:
79:
76:
68:
64:
61:
57:
53:
49:
33:
30:
27:
19:
475:expanding it
464:
418:expanding it
407:
400:
391:
366:
351:
346:
325:
263:
218:
55:
51:
15:
262:are called
514:Categories
338:References
221:numberings
63:computable
303:∘
300:μ
294:ν
250:μ
230:ν
164:⊆
136:⊆
88:→
80::
69:function
67:bijective
20:two sets
365:(1987),
322:Theorems
286:so that
385:0886890
326:By the
181:, i.e.
153:equals
404:
383:
373:
465:This
408:This
60:total
471:stub
414:stub
371:ISBN
242:and
65:and
50:are
54:or
46:of
16:In
516::
381:MR
379:,
334:.
216:.
502:e
495:t
488:v
477:.
445:e
438:t
431:v
420:.
388:.
306:f
297:=
274:f
204:B
201:=
198:)
195:A
192:(
189:f
168:N
161:B
140:N
133:A
113:f
92:N
84:N
77:f
34:B
31:,
28:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
