Θεωρία υπολογισιμότητας: Διαφορά μεταξύ των αναθεωρήσεων

Κυρίως με την Θεωρία των Αναδρομικών Συνόλων και Συναρτήσεων ο χώρος έρευνας της Θεωρίας της Αναδρομής έχει επεκταθεί σε πολλές σχετικές θεωρίες :

Η θεωρία της αναδρομής στη Μαθηματική λογική παραδοσιακά εστιαζόταν στη σχετική υπολογισιμότητα, μια γενίκευση της υπολογισιμότητας Turing,που καθορίζεται χρησιμοποιώντας μια μηχανή χρησμού Turing που παρουσιάστηκε από τον Turing(1939). Μια μηχανή χρησμού Turing, είναι μία υποθετική συσκευή, η οποία εκτός από τις παραδοσιακές ενέργειες μιας μηχανής Turing, μπορεί να κάνει ερωτήσεις για ένα συγκεκριμένο σύνολο ακέραιων αριθμών.Η μηχανή oracle μπορεί να κάνει ερωτήσεις της μορφής <<Είναι το n στο σύνολο oracle;>> Κάθε ερώτηση θα απαντάται άμεσα σωστά ακόμη και αν το σύνολο δεν είναι υπολογίσιμο.

 

Μεγάλο μέρος της πρόσφατης έρευνας για τους βαθμούς Turing έχει επικεντρωθεί στη συνολική δομή του συνόλου των βαθμών Turing και το σύνολο των βαθμών που περιέχουν αναδρομικά αριθμήσιμα σύνολα.Ένα βαθύ θεώρημα του Shore και Slaman (1999) αναφέρει ότι η χαρτογράφηση της συνάρτησης βαθμού x με το βαθμό του άλματος Turing της,είναι προσδιορίσιμο με τη μερική σειρά των βαθμών Turing. Μια πρόσφατη έρευνα από τους Ambos-Spies και Fejer (2006) παρέχει μια επισκόπηση της έρευνας και της ιστορικής εξέλιξης της.

 

Η εν εξελίξει τομέα της έρευνας στη θεωρία αναδρομής μελετά τις σχέσεις αναγωγισιμότητας πλην της αναγωγισιμότητας του Turing . Ο Post (1944) εισήγαγε αρκετές ισχυρές αναγωγισιμότητες, που ονομάστηκαν έτσι επειδή υπαινίσσονται τραπέζι αληθινής αναγωγισιμότητας. Μια μηχανή Turing για την εφαρμογή μιας ισχυρής αναγωγισιμότητας θα υπολογίσει μια συνολική συνάρτηση ανεξάρτητα από το με ποιό oracle παρουσιάζεται. Ασθενείς αναγωγές είναι εκείνες όπου η διαδικασία μείωσης δεν μπορεί να τερματιστεί για όλα τα σύνολα αριθμών. Η αναγωγή του Turing είναι ένα παράδειγμα.

 

Όπως τις:

 

Το Α είναι το ένα προς ένα αναγώγιμο (ή 1-αναγώγιμο) στο Β αν υπάρχει μια συνολική υπολογίσιμη αμφιμονοσήμαντη συνάρτηση τέτοια ώστε κάθε n είναι στην Α αν και μόνο αν το f(n) είναι στο Β.