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

Η '''Θεωρία της Υπολογισιμότητας''' ή '''Θεωρία της Αναδρομής''', είναι ένας κλάδος της [[μαθηματική λογική|μαθηματικής λογικής]], της [[πληροφορική]]ς και της [[Θεωρία υπολογισμού|θεωρίας υπολογισμού]] που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού Turing (=βαθμος μη επιλυσιμότητας) στα μέσα της δεκαετίας του 1930.

Τα βασικά ερωτήματα που απευθύνονται από την Θεωρία Αναδρομής είναι "«Τι σημαίνει για μια συνάρτηση, ορισμένη στους [[φυσικός αριθμός|φυσικούς αριθμού]]ς, ότι είναι υπολογίσιμη;"» και "«Πώς μπορούν μη-υπολογίσιμες συναρτήσεις να κατηγοριοποιηθούν ιεραρχικά ανάλογα με το βαθμό μη-υπολογισιμότητας τους;"». Η απάντηση σε αυτές τις ερωτήσεις οδήγησε σε μία πλούσια θεωρία η οποία ακόμη απασχολεί τους επιστήμονες. Το πεδίο των ερευνών αυτών έχει διευρυνθεί από τότε και πλέον περιέχει την έρευνα της γενικευμένης υπολογισιμότητας και προσδιορισιμότητας. Αξιοσημείωτη είναι η εφεύρεση του κεντρικού συνδυαστικού αντικειμένου της Αναδρομικής Θεωρίας, δηλαδή το Universal Turing Machine,το οποίο προηγείται και προκαθορίζει την εφεύρεση των σύγχρονων υπολογιστών. Ιστορικά , η έρευνα των αλγοριθμικά undecidable συνόλων και συναρτήσεων προέκυψε από διάφορα μαθηματικά προβλήματα που κατέληγαν undecidable. Υπάρχουν πολλές εφαρμογές αυτής της θεωρίας σε άλλους κλάδους των μαθηματικών που δεν επικεντρώνονται απαραίτητα στην undecidability. Στις πρώτες εφαρμογές της περιλαμβάνονταν Higman's embedding theorem , το οποίο συνδέει την Αναδρομική Θεωρία με την Θεωρία των Ομάδων που ήταν αποτέλεσμα των Michael O. Rabin και Anatoly Maltsev στην αλγοριθμική παρουσίαση της άλγεβρας αλλά και την αρνητική λύση του Hilbert's Tenth Problem. Οι πιο νέες εφαρμογές περιλαμβάνουν την αλγοριθμική τυχαιότητα που αποτελεί έρευνα του Theodore Allen Slaman , ο οποίος εφάρμοσε αναδρομικές-θεωρητικές μεθόδους για να επιλύσει προβλήματα [[Αλγεβρική γεωμετρία|Αλγεβρικής Γεωμετρίας]] και η νεότερη του δουλειά εστιάζεται στους κανονικούς αριθμούς για να λύσει προβλήματα της Αναλυτικής Θεωρίας Αριθμών.

Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την [[Θεωρία μοντέλων|Θεωρία Μοντέλων]] και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing Οι θεωρητικοί της Αναδρομής στη μαθηματική λογική συχνά μελετούν τη θεωρία της σχετικής υπολογιστικότητας. Αυτό έρχεται σε αντίθεση με τη θεωρία της αναδρομικής ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνητικών

Πολλά προβλήματα των [[μαθηματικών]] έχει αποδειχθεί ότι είναι άλυτα αφού αυτά τα αρχικά παραδείγματα καθιερώθηκαν. Το 1947, ο Markov και ο Post δημοσίευσαν ανεξάρτητες μελέτες που δείχνουν ότι η λέξη πρόβλημα για υποσύνολα δεν μπορεί να λυθεί αποτελεσματικά. Επεκτείνοντας αυτό το αποτέλεσμα, ο [[Pyotr Novikov]] και ο [[William Boone]] έδειξαν ανεξάρτητα στη δεκαετία του 1950 ότι η [[λέξη πρόβλημα για τις|λέξη πρόβλημα για τις ομάδες]] δεν είναι αποτελεσματικά επιλύσιμο: δεν υπάρχει αποτελεσματική διαδικασία η οποία, δοσμένης μιας λέξης σε μια παρουσιασμένη ομάδα , θα αποφασίσει εάν το στοιχείο που αντιπροσωπεύεται από τη λέξη είναι το στοιχείο της ταυτότητας της [[ομάδας]]. Το 1970, ο [[Yuri|Yuri Matiyasevich ]]<nowiki/>αποδείχθηκε (χρησιμοποιώντας τα αποτελέσματα της [[Julia Robinson]] ) το [[Matiyasevich θεώρημα]] του , πράγμα που σημαίνει ότι [[το δέκατο πρόβλημα του Hilbert]] δεν έχει καμία αποτελεσματική λύση. Το πρόβλημα αυτό ρώτησε αν υπάρχει μια αποτελεσματική διαδικασία για να αποφασιστεί εάν μια [[εξίσωση Diophantine]] επί των ακεραίων έχει μια λύση στα ακέραιοι. [[Ο κατάλογος των μη|Ο κατάλογος των μη λυμένων προβλημάτων]] παρέχει επιπλέον παραδείγματα των προβλημάτων χωρίς υπολογίσιμη λύση.

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

Ο Ράις έδειξε ότι για κάθε μη τετριμμένη κατηγορία C (η οποία περιέχει ορισμένα αλλά όχι όλα τα σύνολα) στο ενδεικτικό σύνολο E = {e: το e στο We είναι στο C} έχει την ιδιότητα ότι είτε το [[πρόβλημα τερματισμού]] ή το συμπλήρωμά της είναι πολλές -ένα αναγώγιμο στο E, δηλαδή, μπορεί να χαρτογραφηθούν με τη χρήση [[αναγωγή|πολλών-μίας αναγωγής]] έως Ε (βλ. [[θεώρημα του Rice]] για περισσότερες λεπτομέρειες). Όμως, πολλά από αυτά τα ενδεικτικά σύνολα είναι ακόμη πιο περίπλοκα από ότι το πρόβλημα τερματισμού. Τα εν λόγω είδη συνόλων μπορούν να ταξινομηθούν χρησιμοποιώντας την [[αριθμητική ιεραρχία]]. Για παράδειγμα,το ενδεικτικό σύνολο FIN της τάξης όλων των πεπερασμένων συνόλων είναι στο επίπεδο Σ2 , το ενδεικτικό σύνολο REC της τάξης όλων των αναδρομικών συνόλων είναι στο επίπεδο Σ3, το ενδεικτικό σύνολο COFIN όλων των ομοτελικών συνόλων είναι επίσης στο επιπέδου Σ3 και το ενδεικτικό σύνολο COMP της κατηγορίας όλων των ολοκληρωμένων συνόλων Turing στο Σ4 . Αυτά τα επίπεδα ιεραρχίας ορίζονται επαγωγικά, Σn+1 και περιέχονται ακριβώς όλα τα σύνολα που είναι αναδρομικά αριθμήσιμα σε σχέση με το Σn. Το Σ1 περιέχει τα αναδρομικά αριθμήσιμα σύνολα.Τα ενδεικτικά σύνολα που δίνονται εδώ είναι πλήρεις ακόμη και για τα επίπεδά τους,δηλαδή όλα τα σύνολα σε αυτά τα επίπεδα μπορεί να είναι πολλά προς ένα αναγώγιμα στα ενδεικτικά δοσμένα σύνολα.

Το πρόγραμμα των [[Αντίστροφα μαθηματικά|αντιστρόφων Μαθηματικών]] ρωτά ποια αξιώματα υπαρκτά από τα σύνολα είναι αναγκαία για να αποδειχθεί συγκεκριμένα θεωρήματα των μαθηματικών σε υποσυστήματα της [[αριθμητική δεύτερη τάξη|αριθμητικής της δεύτερης τάξης]]. Η μελέτη αυτή ξεκίνησε από τον [[Harvey Friedman]] και μελετήθηκε λεπτομερώς από τον Stephen Simpson και άλλους. Ο Simpson (1999) δίνει μια λεπτομερή συζήτηση για το πρόγραμμα. Τα αξιώματα της ύπαρξης των συνόλων υπό ερώτηση αντιστοιχούν ανεπίσημα σε αξιώματα που λένε ότι το δυναμοσύνολο των ακέραιων αριθμών είναι κλειστό υπό διάφορες έννοιες αναγωγής. Το πιο αδύναμο τέτοιο αξίωμα που έχει μελετηθεί σε αντίστροφα μαθηματικά είναι η αναδρομική κατανόηση, η οποία αναφέρει ότι το δυναμοσύνολο των ακεραίων είναι κλειστό υπό την αναγωγή Turing.

Η αρίθμηση είναι μια απαρίθμηση των συναρτήσεων. Έχει δύο παραμέτρους, e και χ και εξάγει την τιμή της συνάρτησης e στην αρίθμηση για την είσοδο x. Οι αριθμήσεις μπορεί να είναι μερικά-αναγώγιμες αν και ορισμένα από τα μέλη τους είναι συνολικά αναγώγιμα, δηλαδή, υπολογίσιμες συναρτήσεις. [[Παραδεκτές αριθμήσεις]] είναι εκείνες στις οποίες όλες οι άλλες μπορούν να μεταφραστούν. Μια [[Friedberg|αρίθμηση Friedberg]] (που ονομάζεται από αυτόν που την ανακάλυψε) είναι η ένα προς ένα αρίθμηση όλων των επιμέρους-αναδρομικών συναρτήσεων, είναι κατ ' ανάγκην μια μη παραδεκτή αρίθμηση. Μεταγενέστερη έρευνα ασχολήθηκε επίσης με αριθμήσεις από άλλες κατηγορίες όπως τις τάξεις των αναδρομικά αριθμήσιμων συνόλων. Ο Goncharov ανακάλυψε για παράδειγμα μια κατηγορία αναδρομικά αριθμήσιμων συνόλων για τα οποία οι αριθμήσεις εμπίπτουν σε δύο κατηγορίες ακριβώς σε σχέση με τους αναδρομικούς ισομορφισμούς.

Το πρόβλημα του Post λύθηκε με μια μέθοδο που ονομάζεται η μέθοδος κατά προτεραιότητας,μια απόδειξη χρήση αυτής της μεθόδου ονομάζεται επιχείρημα προτεραιότητας. Αυτή η μέθοδος χρησιμοποιείται κυρίως για την κατασκευή αναδρομικά αριθμήσιμων συνόλων με συγκεκριμένες ιδιότητες. Για να χρησιμοποιηθεί αυτή η μέθοδος, οι επιθυμητές ιδιότητες του συνόλου που πρόκειται να κατασκευαστεί χωρίστηκαν σε έναν άπειρο κατάλογο των στόχων, που είναι γνωστός ως απαιτήσεις, έτσι ώστε ικανοποιώντας όλες τις απαιτήσεις θα κάνει το κατσκευασμένο σύνολο να έχει τις επιθυμητές ιδιότητες. Κάθε απαίτηση έχει εκχωρηθεί σε ένα φυσικό αριθμό που αντιπροσωπεύει την προτεραιότητα της απαίτησης, έτσι το 0 αποδίδεται στην πιο σημαντική προτεραιότητα, το 1 στη δεύτερη πιο σημαντική, και ούτω καθεξής. Το σύνολο στη συνέχεια κατασκευάζεται σε στάδια, σε κάθε στάδιο προσπαθεί να ικανοποιήσει μία ή περισσότερες από τις απαιτήσεις, είτε με την προσθήκη αριθμών στο σύνολο ή με την απαγόρευση των αριθμών από το σύνολο, έτσι ώστε το τελικό σύνολο να ικανοποιεί την απαίτηση. Μπορεί να συμβεί να ικανοποιείται μία απαίτηση και αυτό να προκαλεί τη μη ικανοποίηση μιας άλλης,η σειρά προτεραιότητας χρησιμοποιείται για να αποφασιστεί τι πρέπει να γίνει σε μια τέτοια περίπτωση. Τα επιχειρήματα Προτεραιότητας έχουν χρησιμοποιηθεί για να λύσουν πολλά προβλήματα στη θεωρία αναδρομής, και έχουν ταξινομηθεί σε μια ιεραρχία με βάση την πολυπλοκότητά τους (Soare 1987). Επειδή τα περίπλοκα επιχειρήματα προτεραιότητας μπορεί να είναι τεχνικά και δύσκολα να ακολουθηθούν, παραδοσιακά θεωρείται σκόπιμο να αποδειχτούν τα αποτελέσματα χωρίς επιχειρήματα προτεραιότητας, ή να διαπιστώσουμε αν τα αποτελέσματα που αποδείχθηκαν με επιχειρήματα προτεραιότητας μπορούν επίσης να αποδειχθούν χωρίς αυτά. Για παράδειγμα, ο Kummer δημοσίευσε ένα έγγραφο σε μια απόδειξη για την ύπαρξη της αρίθμηση του Friedberg χωρίς τη χρήση της μεθόδου προτεραιότητας.

Ένα άλλο σημαντικό ζήτημα είναι η ύπαρξη αυτομορφισμών στις δομές της ανάδρομης θεωρίας . Σε μία από αυτές τις δομές, το Α είναι κάτω από Β αν και μόνο αν η διαφορά συνόλου Β - Α είναι πεπερασμένη. [[Τα Μέγιστα σύνολα]] (όπως ορίζονται στην προηγούμενη παράγραφο) έχουν την ιδιότητα ότι δεν μπορούν να είναι αυτομορφικά σε μη-μέγιστη σύνολα, δηλαδή, εάν υπάρχει ένας αυτομορφισμός των αναδρομικών αριθμητικών συνόλων σύμφωνα με τη δομή που μόλις ανεφέρθη, τότε κάθε μέγιστο σύνολο αντιστοιχίζεται σε ένα άλλο μέγιστο σύνολο. Ο Soare (1974) έδειξε ότι και το αντίστροφο ισχύει, δηλαδή, κάθε δύο μέγιστα σύνολα είναι αυτόμορφα. Έτσι, τα μέγιστα σύνολα σχηματίζουν μια τροχιά, δηλαδή, κάθε αυτομορφία διατηρεί μεγιστοποίηση και οποιαδήποτε δύο μέγιστα σύνολα μετασχηματίζονται το ένα στο άλλο από κάποια αυτομορφία. Ο Harrington έδωσε ένα ακόμη παράδειγμα μιας αυτομορφικής ιδιότητας : αυτής των δημιουργικών συνόλων, των συνόλων που έχουν πολλά-ένα ισοδύναμα με το πρόβλημα τερματισμού. Εκτός από το πλέγμα των αναδρομικά αριθμήσιμων συνόλων, οι αυτομορφισμοί έχουν επίσης μελετηθεί για τη δομή των Turing βαθμών όλων των συνόλων, καθώς και για τη δομή των Turing βαθμών σε r.e. σύνολα. Σε αμφότερες τις περιπτώσεις, o Cooper ισχυρίζεται ότι έχει κατασκευασει μη τετριμμένους αυτομορφισμούς που χαρτογραφούν κάποιους βαθμούς σε άλλους βαθμούς. Αυτη η κατασκευή, ωστόσο, δεν έχει επαληθευτεί και ορισμένοι συνάδελφοί του πιστεύουν ότι η κατασκευή περιέχει σφάλματα και ότι το ζήτημα του κατά πόσον υπάρχει ένας τετριμμένος αυτομορφισμός των βαθμών Turing εξακολουθεί να είναι ένα από τα κύρια εκκρεμή θέματα σε αυτόν τον τομέα (Slaman και Woodin 1986, Ambos-Spies και Fejer 2006).

Αυτός ο κλάδος της θεωρίας της αναδρομής ανέλυσε την ακόλουθη ερώτηση: Για σταθερά ''m'' και ''n'' με 0&nbsp;&lt;&nbsp;''m''&nbsp;&lt;&nbsp;''n'', για την οποία λειτουργεί το Α είναι δυνατόν να υπολογιστεί και για τυχόν διαφορετικές εισόδους n x 1, x 2, ..., x n μια πλειάδα n αριθμών y 1, y 2, ..., yn έτσι ώστε τουλάχιστον το m των εξισώσεων A (x k) = y k να είναι αληθές. Τέτοια σύνολα είναι γνωστά ως (m, n) αναδρομικά σύνολα. Το πρώτο σημαντικό αποτέλεσμα σε αυτόν τον κλάδο της ανάδρομης θεωρίας είναι το αποτέλεσμα του Trakhtenbrot ότι ένα σύνολο είναι υπολογίσιμο αν είναι (m, n) ανάδρομο για κάποιο m, n με 2''m''&nbsp;&gt;&nbsp;''n''. Από την άλλη πλευρά, τα [[ημιανάδρομα]] σύνολα του Jockusch (τα οποία ήταν ήδη γνωστά ανεπίσημα πριν τα εισαγάγει ο Jockusch το 1968 ) αποτελούν παραδείγματα ενός συνόλου που είναι ανάδρομο κατά (m, n) αν και μόνο αν 2''m''&nbsp;&lt;&nbsp;''n''&nbsp;+&nbsp;1. Υπάρχουν αναρίθμητα πολλά απο αυτά τα σύνολα και επίσης κάποια αναδρομικά αριθμητικά αλλά μη-υπολογίσιμα σύνολα του τύπου αυτού. Αργότερα, ο Degtev προέβλεψε την ιεράρχηση των αναδρομικά αριθμήσιμων συνόλων που είναι (1, n + 1), αλλά όχι (1, n). Μετά από μια μακρά φάση της έρευνας από Ρώσους επιστήμονες, το θέμα αυτό έγινε ξανά δημοφιλές στα δυτικά από την πραγματεία του Beigel για οριοθετημένα ερωτήματα, τα οποία συνδέουν τον υπολογισμό της συχνότητας με την προαναφερόμενη οριοθετημένη αναγωγή και άλλες συναφείς έννοιες. Ένα από τα σημαντικότερα αποτελέσματα ήταν Cardinality Θεωρία του Kummer η οποία αναφέρει ότι ένα σύνολο Α είναι υπολογίσιμο αν και μόνο αν υπάρχει n τέτοιο ώστε κάποιος αλγόριθμος απαριθμεί για κάθε πλειάδα των n διαφορετικούς αριθμούς μέχρι n πολλές πιθανές επιλογές αυτού του συνόλου των n αριθμών διασταυρώνεται με το Α. Αυτές οι επιλογές πρέπει να περιέχουν την πραγματική cardinality αλλά να αφήνουν έξω τουλάχιστον μια ψεύτικη.

Η ανάδρομη θεωρία περιλαμβάνει τη μελέτη των γενικευμένων εννοιών του τομέα αυτού, όπως η [[αριθμητική αναγωγή]] , η [[υπεραριθμιτική αναγωγή]] και [[θεωρία της α-αναδρομής]] , όπως περιγράφεται από τον Sacks (1990). Αυτές οι γενικευμένες έννοιες περιλαμβάνουν αναγωγές που δεν μπορούν να εκτελεστούν από μηχανές Turing, αλλά είναι παρ 'όλα αυτά φυσικά γενικεύσεις της αναγωγής του Turing . Οι μελέτες αυτές περιλαμβάνουν προσεγγίσεις για τη διερεύνηση της [[αναλυτικής ιεραρχίας]] η οποία διαφέρει από την [[αριθμητική ιεραρχία]] επιτρέποντας την ποσοτικοποίηση πάνω σε σύνολα των ακεραίων αριθμών εκτός από την ποσοτικοποίηση των ατομικών αριθμών. Οι περιοχές αυτές συνδέονται με τις θεωρίες των καλώς διεταγμένων και τις γραφικές αναπαραστάσεις. Για παράδειγμα, το σύνολο όλων των δεικτών των αναδρομικών (μη δυαδικές) αναπαραστάσεων χωρίς άπειρα κλαδιά είναι πλήρης για το επίπεδο της αναλυτικής ιεραρχίας. Τόσο η αναγωγιμότητα Turing και η υπεραριθμιτική αναγωγή είναι σημαντική στον τομέα της [[αποτελεσματικής περιγραφικής θεωρίας]] του σύνολο . Η ακόμα πιο γενική έννοια των [[βαθμών Κατασκευασιμότητας]] έχει μελετηθεί σε [[θεωρία συνόλων]].

Η Θεωρία της υπολογισιμότητας για τον ψηφιακό υπολογισμό έχει αναπτυχθεί καλά. Η Θεωρία της υπολογισιμότητας είναι λιγότερο καλά αναπτυγμένη για [[αναλογικό υπολογισμό]] που εμφανίζεται σε [[αναλογικούς υπολογιστές]] , [[αναλογική επεξεργασία σήματος]] , [[αναλογικά ηλεκτρονικά]] , [[νευρωνικά δίκτυα]] και συνεχούς χρόνου [[θεωρία ελέγχου]] διαμορφωμένη από [[διαφορικές εξισώσεις]] και συνεχή [[δυναμικά συστήματα]] (Orponen 1997, Moore 1996).

Υπάρχουν στενοί δεσμοί μεταξύ του βαθμού Turing ενός συνόλου φυσικών αριθμών και της δυσκολίας (απο πλευράς [[αριθμητικής ιεραρχίας]]) προσδιορισμού αυτού του συνόλου χρησιμοποιώντας [[Λογική πρώτου βαθμού|Λογική Πρώτου Βαθμού]].Αυτή η σχέση έγινε εφικτή με την βοήθεια του [[θεωρήματος του Post]]. Μία λιγότερο ακριβής απόδειξη παρουσιάστηκε απο τον [[Κουρτ Γκέντελ]] με τις αποδείξεις του στα [[θεωρήματα ολοκληρωσιμότητας]] και [[μη ολοκληρωσιμότητας]].οι Οι αποδείξεις του Γκέντελ εξηγούν ότι ένα σύνολο λογικών συνεπειών μίας δυναμικής Λογικής Πρώτου Βαθμού είναι ένα [[αναδρομικά αριθμήσιμο σύνολο]] και αν η θεωρία ειναι αρκετά ισχυρή τότε αυτό το σύνολο θα είναι μη υπολογίσιμο. Παρομοίως το [[Θεώρημα της μη-Προσδιορισιμότητας του Τάρσκι]] Similarly, Tarski's μπορεί να ερμηνευτεί τόσο από την άποψη της προσδιορισιμότητας όσο και της υπολογισιμότητας.

Ο κλάδος της [[Θεωρίας Αποδείξεων]] περιλαμβάνει την μελέτη της αριθμητικής δεύτερης ταξης και τα [[Αξιώματα Πεάνο]] όπως επίσης και τυπικές θεωρίες των φυσικών πιο αδύναμες από τα Αξιώματα Πεάνο.Μία μέθοδος κατηγοριοποιήσης της ισχύς αυτών των αδύναμων συστημάτων γίνεται με τον χαρακτηρισμό για ποιες υπολογίσμες συναρτήσεις το σύστημα μπορει να αποδειχθεί [[πλήρες]] (βλ. Fairtlough and Wainer (1998)).Για παράδειγμα ,στην [[θεμελιωδώς αναδρομική αριθμητική]] οποιαδήποτε συνάρτηση που ειναι πλήρης ειναι [[θεμελιωδώς αναδρομική]] , ενώ τα [[Αξιώματα Πεάνο]] αποδεικνύουν ότι συναρτήσεις όπως η [[συνάρτηση του Ackermann]] , οι οποίες δεν είναι θεμελιωδώς αναδρομικές ,είναι πλήρης,Επομένως δεν αποδεικνύεται για όλες τις πλήρης-υπολογίσιμες συναρτήσεις οτι ειναι πλήρης και στην Αριθμητική Πεάνο.Μάλιστα μία τέτοια συνάρτηση δίνεται απο το θεώρημα Goodstein.

Το πεδίο της μαθηματικής λογικής που ασχολείται με την υπολογισιμότητα και τις γενικεύσεις της έχει χαρακτηριστεί ως «θεωρία αναδρομής» από τις πρώτες ημέρες της. Ο [[Robert I. Soare]] , ένας εξέχων ερευνητής στον τομέα, πρότεινε (Soare 1996) ότι το πεδίο θα πρέπει να ονομάζεται «θεωρία υπολογισιμότητας "». Ισχυρίζεται ότι η ορολογία του Τούρινγκ που χρησιμοποιεί τη λέξη «υπολογίσιμο» είναι πιο φυσική και πιο ευρέως κατανοητή από την ορολογία που χρησιμοποιεί τη λέξη «αναδρομική» που θεσπίστηκε από τον Kleene. Πολλοί σύγχρονοι ερευνητές έχουν αρχίσει να χρησιμοποιούν αυτή την εναλλακτική ορολογία. Αυτοί οι ερευνητές χρησιμοποιούν επίσης την ορολογία, όπως μερικά υπολογίσιμη συνάρτηση και υπολογισίμως αριθμήσιμο σύνολο αντί για μερικά αναδρομική συνάρτηση και αναδρομικά αριθμήσιμα σύνολα. Δεν έχουν όλοι οι ερευνητές αυτή την πεποίθηση, ωστόσο, όπως εξήγησε ο Fortnow και Simpson. Ορισμένοι σχολιαστές υποστηρίζουν ότι τόσο το όνομα θεωρία της αναδρομής όσο και το όνομα θεωρία της υπολογισιμότητας αποτυγχάνουν να μεταδώσουν το γεγονός ότι τα περισσότερα από τα αντικείμενα που μελετήθηκαν στη θεωρία αναδρομής δεν είναι υπολογίσιμα. Ο Rogers (1967) πρότεινε ότι μια βασική ιδιότητα της θεωρίας αναδρομής είναι ότι τα αποτελέσματα και οι δομές της θα πρέπει να αμετάβλητες στο πλαίσιο υπολογίσιμων [[συναρτήσεων]] για τους φυσικούς αριθμούς (η πρόταση αυτή εμπνέεται από τις ιδέες του [[προγράμματος Erlangen]] στη γεωμετρία). Η ιδέα είναι ότι ένα υπολογίσιμη συνάρτηση απλώς μετονομάζει τους αριθμούς σε μια σειρά, αντί να αναγράφει κάθε δομή στο σύνολο, ακριβώς όπως και η περιστροφή του Ευκλείδειου επιπέδου δεν αλλάζει οποιαδήποτε γεωμετρική όψη των γραμμών που χαράσσονται σε αυτό. Εφόσον κάθε δύο άπειρα υπολογίσιμα σύνολα συνδέονται με υπολογίσιμη συνάρτηση, η παρούσα πρόταση προσδιορίζει όλα τα άπειρα υπολογίσιμα σύνολα (τα πεπερασμένα σύνολα υπολογίσιμα σύνολα θεωρούνται ως ασήμαντο). Σύμφωνα με τον Rogers, τα σύνολα των τόκων στη θεωρία της αναδρομής είναι τα μη-υπολογίσιμα σύνολα, χωρισμένα σε κατηγορίες ισοδυναμίας από υπολογίσιμες συναρτήσεις των ακεραίων αριθμών.

Η κύρια επαγγελματική οργάνωση για τη θεωρία της αναδρομής είναι [[η Ένωση της Συμβολικής Λογικής]] , η οποία οργανώνει διάφορα ερευνητικά συνέδρια κάθε χρόνο. Η διεπιστημονική ερευνητική οργάνωση [[Υπολογισιμότητα στην Ευρώπη]] (CiE) διοργανώνει επίσης μια σειρά ετήσιων συνεδρίων. Το συνέδριο CiE 2012 ήταν η διάσκεψη εκατονταετίας [[Turing]] , που πραγματοποιήθηκε στο Cambridge, στο πλαίσιο του [[έτους Alan Turing]].

# Το πλήρες χαρτί μπορεί επίσης να βρεθεί στις σελίδες 150ff (με σχολιασμό από τον Charles Parsons στο 144ff) σε Feferman et al. συντάκτες 1990 Kurt Gödel Τόμος ΙΙ Εκδόσεις 1938-1974, Oxford University Press, Νέα Υόρκη,  [[ISBN 978-0-19-514721-6]]. Και οι δύο έχουν τυπώσει την ακόλουθη υποσημείωση * στον όγκο Davis από τον Κουρτ Γκέντελ το 1965: "«Για να είμαι πιο ακριβής: η λειτουργία των ακεραίων είναι υπολογίσιμη σε κάθε επίσημο σύστημα που περιέχει αριθμητική αν και μόνο αν είναι υπολογίσιμη στην αριθμητική, όπου η συνάρτηση f ονομάζεται υπολογίσιμη στο S αν υπάρχει σε ένα υπολογίσιμο S που αντιπροσωπεύει την f» (σελ. 150).

# [[Μαθηματικές|Μαθηματικές αναζητήσεις]] για τους τίτλους όπως «υπολογίσιμα enumerable"» και "«c.e."» δείχνουν ότι πολλές εργασίες έχουν δημοσιευθεί με αυτήν την ορολογία, καθώς και με την άλλη.

# Lance Fortnow, "«[[Είναι Αναδρομική, Computable ή να αποφασισθεί;]]"» 15.02.2004, πρόσβαση 09/01/2006.

# Stephen G. Simpson, "«[[Τι είναι η θεωρία computability;]]"» FOM κατάλογο ηλεκτρονικού ταχυδρομείου, 08.24.1998, 01.09.2006 πρόσβαση.

# Harvey Friedman, «[[η θεωρία Μετονομασία αναδρομής]],"» λίστα email FOM, 08.28.1998, 01.09.2006 πρόσβαση.

:* K. Ambos-Spies and P. Fejer, 2006. "«Degrees of Unsolvability."» Unpublished preprint.

:* H. Enderton, 1977. "«Elements of Recursion Theory."» ''Handbook of Mathematical Logic'', edited by J. Barwise, North-Holland (1977), pp. 527–566. ISBN 0-7204-2285-X

:* M. Fairtlough and S. Wainer, 1998. "«Hierarchies of Provably Recursive Functions"». In ''Handbook of Proof Theory'', edited by S. Buss, Elsevier (1998).

:* Burgin, M. and Klinger, A. "«Experience, Generations, and Limits in Machine Learning."» ''Theoretical Computer Science'' vτομ. 317, No. 1/3, 2004, pp. 71–91

:* A. Church, 1936a. "«An unsolvable problem of elementary number theory."» ''American Journal of Mathematics'' vτομ. 58, pp. 345–363. Reprinted in "The Undecidable", M. Davis ed., 1965.

:* A. Church, 1936b. "«A note on the Entscheidungsproblem."» ''Journal of Symbolic Logic'' v. 1, n. 1, and v. 3, n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.

:* R. M. Friedberg, 1958. "Three theorems on recursive enumeration: I.

Decomposition, II. Maximal Set, III. Enumeration without repetition." «''The Journal of Symbolic Logic''», v. 23, pp. 309–316.

:* L. Harrington and R. I. Soare, 1991. "«Post's Program and incomplete recursively enumerable sets"», ''Proceedings of the National Academy of Sciences of the USA'', volume 88, pages 10242—10246.

:* C. Jockusch jr, "«Semirecursive sets and positive reducibility"», ''Trans. Amer. Math. Soc.'' '''137''' (1968) 420-436

:* S. C. Kleene and E. L. Post, 1954. "«The upper semi-lattice of degrees of recursive unsolvability."» ''Annals of Mathematics'' vτομ. 2 n. 59, 379–407.

:* Moore, C. (1996). "«Recursion theory on the reals and continuous-time computation"». ''Theoretical Computer Science''. CiteSeerX: 10.1.1.6.5519.

:* J. Myhill, 1956. "«The lattice of recursively enumerable sets."» ''The Journal of Symbolic Logic'', vτομ. 21, pp. 215–220.

:* Orponen, P. (1997). "«A survey of continuous-time computation theory"». ''Advances in algorithms, languages, and complexity''. CiteSeerX: 10.1.1.53.1991.

:* E. Post, 1944, "«Recursively enumerable sets of positive integers and their decision problems"», ''Bulletin of the American Mathematical Society'', volumeτομ. 50, pagesσελίδες 284–316.

:* E. Post, 1947. "«Recursive unsolvability of a problem of Thue."» ''Journal of Symbolic Logic'' v. 12, pp. 1–11. Reprinted in "The Undecidable", M. Davis ed., 1965.

:* Shore, Richard A.; Slaman, Theodore A. (1999), "«Defining the Turing jump"», ''Mathematical Research Letters'' '''6''': 711–722, ISSN 1073-2780, MR 1739227

:* T. Slaman and W. H. Woodin, 1986. "«Definability in the Turing degrees."» ''Illinois J. Math.'' vτομ. 30 n. 2, pp. 320–334.

:* R. I. Soare, 1974. "«Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets."» ''Annals of Mathematics'', vτομ. 100, pp. 80–120.

:* A. Turing, 1937. "«On computable numbers, with an application to the Entscheidungsproblem."» ''Proceedings of the London Mathematics Society'', ser. 2 vτομ. 42, pp. 230–265. Corrections ''ibid.'' v. 43 (1937) pp. 544–546. Reprinted in "The Undecidable", M. Davis ed., 1965. PDF from comlab.ox.ac.uk

:* A. Turing, 1939. "«Systems of logic based on ordinals»." «''Proceedings of the London Mathematics Society''», ser. 2 vτομ. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.