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

Ο Rogers (1967) πρότεινε ότι μια βασική ιδιότητα της θεωρίας αναδρομής είναι ότι τα αποτελέσματα και οι δομές της θα πρέπει να αμετάβλητες στο πλαίσιο υπολογίσιμων συναρτήσεων για τους φυσικούς αριθμούς (η πρόταση αυτή εμπνέεται από τις ιδέες του προγράμματος Erlangen στη γεωμετρία). Η ιδέα είναι ότι ένα υπολογίσιμη συνάρτηση απλώς μετονομάζει τους αριθμούς σε μια σειρά, αντί να αναγράφει κάθε δομή στο σύνολο, ακριβώς όπως και η περιστροφή του Ευκλείδειου επιπέδου δεν αλλάζει οποιαδήποτε γεωμετρική όψη των γραμμών που χαράσσονται σε αυτό. Εφόσον κάθε δύο άπειρα υπολογίσιμα σύνολα συνδέονται με υπολογίσιμη συνάρτηση, η παρούσα πρόταση προσδιορίζει όλα τα άπειρα υπολογίσιμα σύνολα (τα πεπερασμένα σύνολα υπολογίσιμα σύνολα θεωρούνται ως ασήμαντο). Σύμφωνα με τον Rogers, τα σύνολα των τόκων στη θεωρία της αναδρομής είναι τα μη-υπολογίσιμα σύνολα, χωρισμένα σε κατηγορίες ισοδυναμίας από υπολογίσιμες συναρτήσεις των ακεραίων αριθμών.

 

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