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

Οι κύριες ερωτήσεις που απαντώνται από την ανάδρομη θεωρία είναι: "Τι σημαίνει για μια συνάρτηση ακέραιων αριθμών να είναι υπολογίσιμη;" και "Πως μπορούν οι μη-υπολογίσιμες συναρτήσεις να ταξινομηθούν σε μια ιεραρχία βασισμένη στο επίπεδο της μη-υπολογισιμότητάς τους;"Οι απαντήσεις σε αυτές τις ερωτήσεις έχουν οδηγήσει σε μια πλούσια θεωρία που ερευνάται ακόμη ενεργά.Το πεδίο από τότε έχει αναπτυχθεί για να συμπεριλάβει τη μελέτη της γενικευμένης υπολογισιμότητας και του καθορισμού εννοιών. Αξιοσημείωτα, η ανακάλυψη του κεντρικού συνδυαστικού αντικειμένου της Ανάδρομης Θεωρίας, της Παγκόσμιας μηχανής αναδιάρθρωσης είναι πρόγονος και προκαθορίζει την ανακάλυψη των μοντέρνων υπολογιστών. Historically,Ιστορικά theη studyμελέτη ofτων algorithmicallyαλγοριθμικά undecidableάλυτων setsσυνόλων andκαι functionsσυναρτήσεων wasπροερχόταν motivatedαπό byδιάφορα variousμαθηματικά problemsπροβλήματα inπου mathematicsαποδείχθηκαν that turned to be undecidable; for example, word problem for groups and the likeάλυτα. There are several applications of the theory to other branches of mathematics that do not necessarily concentrate on undecidability. The early applications include the celebrated Higman's embedding theorem that provides a link between recursion theory and group theory, results of Michael O. Rabin and Anatoly Maltsev on algorithmic presentations of algebras, and the negative solution to Hilbert's Tenth Problem. The more recent applications include algorithmic randomness, results of Soare et al. who applied recursion-theoretic methods to solve a problem in algebraic geometry, and the very recent work of Slaman et al. on normal numbers that solves a problem in analytic number theory.