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

μ
μ.επιμέλεια, +κατ
μ (μ.επιμέλεια, +κατ)
Η '''Θεωρία της Υπολογισιμότητας''' ή '''Θεωρία της Αναδρομής''', είναι ένας κλάδος της [[μαθηματική λογική|μαθηματικής λογικής]], της [[πληροφορική]]<nowiki/>ς και της [[Θεωρία υπολογισμού|θεωρίας υπολογισμού]] που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού Turing(=βαθμος μη επιλυσιμότητας) στα μέσα της δεκαετίας του 1930.
 
Τα βασικά ερωτήματα που απευθύνονται από την Θεωρία Αναδρομής είναι "Τι σημαίνει για μια συνάρτηση, ορισμένη στους [[φυσικός αριθμός|φυσικούς αριθμού]]<nowiki/>ς,ότι είναι υπολογίσιμη;" και "Πώς μπορούν μη-υπολογίσιμες συναρτήσεις να κατηγοριοποιηθούν ιεραρχικά ανάλογα με το βαθμό μη-υπολογισιμότητας τους;". Η απάντηση σε αυτές τις ερωτήσεις οδήγησε σε μία πλούσια θεωρία η οποία ακόμη απασχολεί τους επιστήμονες.Το πεδίο των ερευνών αυτών έχει διευρυνθεί από τότε και πλέον περιέχει την έρευνα της γενικευμένης υπολογισιμότητας και προσδιορισιμότητας. Αξιοσημείωτη είναι η εφεύρεση του κεντρικού συνδυαστικού αντικειμένου της Αναδρομικής Θεωρίας,δηλαδή το Universal Turing Machine,το οποίο προηγείται και προκαθορίζει την εφεύρεση των σύγχρονων υπολογιστών. Ιστορικά ,η έρευνα των αλγοριθμικά undecidable συνόλων και συναρτήσεων προέκυψε από διάφορα μαθηματικά προβλήματα που κατέληγαν undecidable. Υπάρχουν πολλές εφαρμογές αυτής της θεωρίας σε άλλους κλάδους των μαθηματικών που δεν επικεντρώνονται απαραίτητα στην undecidability.Στις πρώτες εφαρμογές της περιλαμβάνονταν Higman's embedding theorem ,το οποίο συνδέει την Αναδρομική Θεωρία με την Θεωρία των Ομάδων που ήταν αποτέλεσμα των Michael O. Rabin και Anatoly Maltsev στην αλγοριθμική παρουσίαση της άλγεβρας αλλά και την αρνητική λύση του Hilbert's Tenth Problem. Οι πιο νέες εφαρμογές περιλαμβάνουν την αλγοριθμική τυχαιότητα που αποτελεί έρευνα του Theodore Allen Slaman ,ο οποίος εφάρμοσε αναδρομικές-θεωρητικές μεθόδους για να επιλύσει προβλήματα [[Αλγεβρική γεωμετρία|Αλγεβρικής Γεωμετρίας]] και η νεότερη του δουλειά εστιάζεται στους κανονικούς αριθμούς για να λύσει προβλήματα της Αναλυτικής Θεωρίας Αριθμών.
 
Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την [[Θεωρία μοντέλων|Θεωρία Μοντέλων]] και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing.
κοινοτήτων, ωστόσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε από τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.
 
=== '''Υπολογίσιμα και μη υπολογίσιμα σύνολα.''' ===
Η Αναδρομή θεωρία προέρχεται από τη δεκαετία του 1930, με το έργο του [[Kurt Gödel , Alonzo Church , Alan Turing , Stephen Kleene]] και[[Emil Post| Emil Post.]]
 
Τα θεμελιώδη αποτελέσματα που αποκόμισαν οι ερευνητές εγκαθίδρυσαν την [[αναδιαρθρωτική υπολογισιμότητα]] ως σωστή επισημοποίησης της άτυπης ιδέα του αποτελεσματικού υπολογισμού. Αυτά τα αποτελέσματα οδήγησαν τον [[Stephen Kleene]] (1952) για να πλάσει τα δύο ονόματα "Church's thesis" (Kleene 1952:300) και «Turing's Thesis» (Kleene 1952:376). Σήμερα αυτά συχνά θεωρούνται ως μια ενιαία υπόθεση η [[Church–Turing|Church–Turing thesis]] η οποία ορίζει ότι κάθε [[λειτουργία]] που είναι[[ υπολογίσιμη]] από τον [[αλγόριθμο]] είναι μια υπολογίσιμη συνάρτηση . Αν και αρχικά σκεπτικός, από το 1946 ο Gödel τάχθηκε υπέρ αυτής της διατριβής:
 
": «Ο Tarski τόνισε στην ομιλία του (και νομίζω δικαίως) τη μεγάλη σημασία της έννοιας της γενικής αναδρομής (ή του υπολογιστικού περιβάλλοντος του Turing). Μου φαίνεται ότι η σημασία αυτή σε μεγάλο βαθμό οφείλεται στο γεγονός ότι με αυτήν την έννοια για πρώτη φορά κατόρθωσε κάποιος να δώσει μια απόλυτη έννοια σε μια ενδιαφέρουσα επιστημολογική αντίληψη, δηλαδή χωρίς να εξαρτάται από τον φορμαλισμό που επιλέγεται. (Gοdel 1946 στο Davis 1965:84).»
 
Με τον ορισμό του αποτελεσματικού υπολογισμού ήρθαν οι πρώτοι αποδείξεις ότι υπάρχουν προβλήματα στα μαθηματικά που δεν μπορούν να [[αποφασιστούν]] αποτελεσματικά . Ο Chyrch (1936a, 1936b) και ο Turing (1936), εμπνευσμένοι από τεχνικές που χρησιμοποιούνται από τον Γκέντελ (1931) για να αποδείξουν τη μη πληρότητα των θεωρημάτων του , ανεξάρτητα κατέδειξαν ότι το [[ Entscheidungs πρόβλημα ]] δεν λύνεται αποτελεσματικά. Το αποτέλεσμα έδειξε ότι δεν υπάρχει αλγοριθμική διαδικασία που μπορεί σωστά να αποφασίσει αν κάποια αυθαίρετη μαθηματική πρόταση είναι αληθής ή ψευδής.
 
Πολλά προβλήματα των [[μαθηματικών]] έχει αποδειχθεί ότι είναι άλυτα αφού αυτά τα αρχικά παραδείγματα καθιερώθηκαν. Το 1947, ο Markov και ο Post δημοσίευσαν ανεξάρτητες μελέτες που δείχνουν ότι η λέξη πρόβλημα για υποσύνολα δεν μπορεί να λυθεί αποτελεσματικά. Επεκτείνοντας αυτό το αποτέλεσμα, ο[[ Pyotr Novikov]] και ο [[William Boone]] έδειξαν ανεξάρτητα στη δεκαετία του 1950 ότι η [[λέξη πρόβλημα για τις|λέξη πρόβλημα για τις ομάδες]] δεν είναι αποτελεσματικά επιλύσιμο: δεν υπάρχει αποτελεσματική διαδικασία η οποία, δοσμένης μιας λέξης σε μια παρουσιασμένη ομάδα , θα αποφασίσει εάν το στοιχείο που αντιπροσωπεύεται από τη λέξη είναι το στοιχείο της ταυτότητας της [[ομάδας]]. Το 1970, ο [[Yuri|Yuri Matiyasevich ]]<nowiki/>αποδείχθηκε (χρησιμοποιώντας τα αποτελέσματα της [[Julia Robinson]] ) το [[Matiyasevich θεώρημα]] του , πράγμα που σημαίνει ότι [[το δέκατο πρόβλημα του Hilbert]] δεν έχει καμία αποτελεσματική λύση. Το πρόβλημα αυτό ρώτησε αν υπάρχει μια αποτελεσματική διαδικασία για να αποφασιστεί εάν μια [[εξίσωση Diophantine]] επί των ακεραίων έχει μια λύση στα ακέραιοι. [[Ο κατάλογος των μη|Ο κατάλογος των μη λυμένων προβλημάτων]] παρέχει επιπλέον παραδείγματα των προβλημάτων χωρίς υπολογίσιμη λύση.
Η μελέτη για το ποιες μαθηματικές κατασκευές μπορούν να πραγματοποιηθούν αποτελεσματικά μερικές φορές ονομάζεται '''αναδρομικά μαθηματικά'''. Το Εγχειρίδιο των Αναδρομικών Μαθηματικών (Ershov et al. 1998) καλύπτει πολλά από τα γνωστά αποτελέσματα σε αυτόν τον τομέα.
 
== '''Πεδία Έρευνας''' ==
Κυρίως με την Θεωρία των Αναδρομικών Συνόλων και Συναρτήσεων ο χώρος έρευνας της Θεωρίας της Αναδρομής έχει επεκταθεί σε πολλές σχετικές θεωρίες :
Κυρίως με την Θεωρία των Αναδρομικών Συνόλων και Συναρτήσεων ο χώρος έρευνας της Θεωρίας της Αναδρομής έχει επεκταθεί σε πολλές σχετικές θεωρίες :
===== '''Σχετική Υπολογισιμότητα και Βαθμός Turing''' =====
Κύρια άρθρα: [[Μείωση Turing]] και [[Βαθμός Turing]]
 
===== '''Σχετική Υπολογισιμότητα και Βαθμός Turing''' =====
Η θεωρία της αναδρομής στη Μαθηματική λογική παραδοσιακά εστιαζόταν στη σχετική υπολογισιμότητα, μια γενίκευση της υπολογισιμότητας Turing,που καθορίζεται χρησιμοποιώντας μια [[μηχανή Turing]] που παρουσιάστηκε από τον Turing(1939). Μια μηχανή χρησμού Turing, είναι μία υποθετική συσκευή, η οποία εκτός από τις παραδοσιακές ενέργειες μιας μηχανής Turing, μπορεί να κάνει ερωτήσεις για ένα συγκεκριμένο σύνολο ακέραιων αριθμών.Η μηχανή oracle μπορεί να κάνει ερωτήσεις της μορφής <<«Είναι το n στο σύνολο oracle;>>» Κάθε ερώτηση θα απαντάται άμεσα σωστά ακόμη και αν το σύνολο δεν είναι υπολογίσιμο.
 
Ανεπίσημα, ένα σύνολο ακεραίων αριθμών Α είναι [[αναγώγιμο]] σε ένα σύνολο Β αν υπάρχει μια μηχανή oracle που σωστά εάν οι αριθμοί είναι στο Α όταν εκτελούνται με το Β, όπως στο σύνολο oracle (σε αυτή την περίπτωση, το σύνολο Α επίσης λέγεται ότι είναι (σχετικά) υπολογίσιμο από το Β και το Β μπορεί να αναχθεί στο Α τότε το σύνολο λέγεται ότι έχουν τον ίδιο [[βαθμός Turing|βαθμό Turing]] (ονομάζεται επίσης βαθμός unsolvability). [[Ο βαθμός Turing]] ενός συνόλου δίνει ένα ακριβές μέτρο του πόσο μη-υπολογίσιμο είναι το σύνολο.
Τα φυσικά παραδείγματα των συνόλων που δεν είναι υπολογίσιμα, συμπεριλαμβανομένων πολλών διαφορετικών συνόλων που κωδικοποιούν παραλλαγές του [[πρόβλημα τερματισμού|προβλήματος τερματισμού]], έχουν δύο κοινές ιδιότητες:
 
1.#Είναι[[ αναδρομικά αριθμήσιμα]], και<br />
2.#Κάθε ένα μπορεί να μεταφραστεί σε οποιοδήποτε άλλο μέσω [[πολλών-μίας μείωσης]]. Δηλαδή, δεδομένων τέτοιων συνόλων Α και Β, υπάρχει μία συνολική λειτουργία τέτοια ώστε Α={x:f(x)∈B} Αυτά τα σύνολα λέγεται ότι είναι πολλές-ένα ισοδύναμο (ή m-ισοδύναμο).
 
Οι πολλές-μια μειώσεις είναι «ισχυρότερες» από τις μειώσεις Turing: εάν ένα σύνολο Α είναι αναγώγιμο σε ένα σύνολο Β, τότε το Α μπορεί να αναχθεί σε B, αλλά το αντίστροφο δεν είναι πάντα εφικτό. Παρά το γεγονός ότι τα φυσικά παραδείγματα μη-υπολογίσιμων συνόλων είναι όλα πολλά-ένα ισοδύναμα, είναι δυνατόν να κατασκευαστούν αναδρομικά αριθμήσιμα σύνολα Α και Β, έτσι ώστε το Α να ανάγεται στο Β, αλλά όχι πολλά-ένα αναγώγιμο στο Β. Μπορεί να δειχθεί ότι κάθε αναδρομικά αριθμήσιμα σύνολο είναι πολλά-ένα αναγώγιμο στο πρόβλημα τερματισμού, και έτσι το πρόβλημα τερματισμού είναι το πιο περίπλοκο αναδρομικά αριθμήσιμα σύνολο σε σχέση με πολλές-ένα αναγωγές και με αναφορά προς την αναγωγή Turing. Ο Post (1944) ρώτησε αν κάθε αναδρομικά αριθμήσιμα σύνολο είναι είτε υπολογίσιμο ή Turing ισοδύναμο με το πρόβλημα τερματισμού, δηλαδή, αν δεν υπάρχει αναδρομικά αριθμήσιμα σύνολο με ένα βαθμό Turing ενδιάμεσο μεταξύ των δύο.
 
Ως ενδιάμεσα αποτελέσματα, ο Post όρισε ακέραιους τύπους αναδρομικά αριθμήσιμων συνόλων όπως τα [[απλά, υπεραπλά και υπέρ-υπεραπλά σύνολα]]. Ο Post έδειξε ότι αυτά τα σύνολα είναι αυστηρά μεταξύ των υπολογίσιμων συνόλων και του προβλήματος τερματισμού σε σχέση με την πολλές-μια αναγωγιμότητα. Ο Post έδειξε επίσης ότι ορισμένοι από αυτούς είναι απολύτως ενδιάμεσο προϊόν υπό άλλες έννοιες αναγωγιμότητας ισχυρότερες από ότι η αναγωγιμότητα του Turing . Αλλά ο Post άφησε ανοιχτό το κύριο πρόβλημα της ύπαρξης των αναδρομικά αριθμήσιμων συνόλων με ενδιάμεσο βαθμό Turing,το πρόβλημα αυτό έγινε γνωστό ως το [[πρόβλημα του Post]]. Μετά από δέκα χρόνια, ο Kleene και ο Post το 1954 έδειξαν ότι υπάρχουν ενδιάμεσοι βαθμοί Turing μεταξύ αυτών τα υπολογίσιμα σύνολα και το πρόβλημα τερματισμού, αλλά απέτυχαν να δείξουν ότι κάποια από αυτές τις μοίρες περιλαμβάνει κάποιο αναδρομικά αριθμήσιμα σύνολο. Πολύ σύντομα μετά από αυτό, ο Friedberg και ο Muchnik ανεξάρτητα έλυσαν το πρόβλημα του Post κατά τη διαπίστωση της ύπαρξης αναδρομικά αριθμήσιμων συνόλων με ενδιάμεσο βαθμό. Αυτή το πρωτοποριακό αποτέλεσμα άνοιξε μια ευρεία μελέτη των βαθμών Turing των αναδρομικά αριθμήσιμων συνόλων που αποδείχθηκε ότι έχουν μια πολύ περίπλοκη και μη τετριμμένη δομή.
 
Υπάρχουν αμέτρητα πολλά σύνολα που δεν είναι αναδρομικά αριθμήσιμα, καθώς και η διερεύνηση των Turing βαθμών όλων των συνόλων είναι τόσο κεντρική στη θεωρία αναδρομής και τη διερεύνηση των αναδρομικά αριθμήσιμων βαθμών Turing. Πολλοί βαθμοί με ειδικές ιδιότητες κατασκευάστηκαν ως υπεράνοσοι χωρίς βαθμούς όπου κάθε λειτουργία υπολογίσιμη σε σχέση με αυτό το βαθμό είναι μεγενθυμένη από μια υπολογίσιμη συνάρτηση. Υψηλούς βαθμούς σε σχέση με τους οποίους μπορεί κανείς να υπολογίσει μια συνάρτηση f η οποία κυριαρχεί σε κάθε υπολογίσιμη συνάρτηση ''g'', με την έννοια ότι υπάρχει μια σταθερά ''c'', ανάλογη με τη ''g'' τέτοια ώστε ''g(x)< &lt; f(x)'' γιαfor κάθεall ''x>c &gt; c'', τυχαίοι βαθμοί που περιέχουν [[αλγοριθμικά τυχαία σύνολα]]. 1-γενικοί βαθμοί ενός 1-γενικού συνόλου.
 
Η μελέτη των αυθαίρετων (όχι κατ ' ανάγκη αναδρομικά αριθμήσιμων) βαθμών Turing περιλαμβάνει τη μελέτη του [[άλματος Turing]]. Λαμβάνοντας υπόψη ένα σύνολο A, το Turing άλμα του Α είναι ένα σύνολο των φυσικών αριθμών που κωδικοποιεί μια λύση για το πρόβλημα τερματισμού για τις μηχανές Turing που τρέχουν με χρησμό Α. Το Turing άλμα του κάθε σετ είναι πάντα με υψηλότερο βαθμό Turing από το αρχικό σύνολο, και ένα θεώρημα του Friedburg δείχνει ότι κάθε σύνολο που υπολογίζει το πρόβλημα τερματισμού μπορεί να ληφθεί ως Turing άλμα του ενός άλλου συνόλου. Το [[θεώρημα του Post]], καθιερώνει μια στενή σχέση μεταξύ της λειτουργίας του άλματος Turing και της [[αριθμητικής ιεραρχίας]] , η οποία είναι μια κατάταξη ορισμένων υποσυνόλων των φυσικών αριθμών με βάση το πόσο μπορούν να οριστικοποιηθούν στην αριθμητική.
 
Μεγάλο μέρος της πρόσφατης έρευνας για τους βαθμούς Turing έχει επικεντρωθεί στη συνολική δομή του συνόλου των βαθμών Turing και το σύνολο των βαθμών που περιέχουν αναδρομικά αριθμήσιμα σύνολα.Ένα βαθύ θεώρημα του Shore και Slaman (1999) αναφέρει ότι η χαρτογράφηση της συνάρτησης βαθμού x με το βαθμό του άλματος Turing της,είναι προσδιορίσιμο με τη μερική σειρά των βαθμών Turing. Μια πρόσφατη έρευνα από τους Ambos-Spies και Fejer (2006) παρέχει μια επισκόπηση της έρευνας και της ιστορικής εξέλιξης της.
 
===== '''Άλλες Αναγωγισιμότητες''' =====
Κύρια άρθρα: [[Μείωση (θεωρία αναδρομής)]]
 
Όπως τις:
 
Αυτό είναι ουσιαστικά η αναγωγή ένα;Μία προς ένα χωρίς τον περιορισμό ότι το f είναιμία αμφιμονοσήμαντο.αναγωγισιμότητα: Το Α είναι πολλοίτο ένα προς ένα αναγώγιμο (ή m1-αναγώγιμηαναγώγιμο) στο Β, αν υπάρχει μια συνολικάσυνολική υπολογίσιμη [[Συνάρτηση|αμφιμονοσήμαντη συνάρτηση,]] έτσιτέτοια ώστε κάθε n ανήκειείναι στοστην AΑ αν και μόνο αν το f(n) είναι στο Β.
===== [[Μία προς μία αναγωγισιμότητα]] =====
Το;Πολλές Απρος μία αναγωγισιμότητα: Αυτό είναι τοουσιαστικά η αναγωγή ένα προς ένα χωρίς τον περιορισμό ότι το f είναι αμφιμονοσήμαντο. Το Α είναι πολλοί προς ένα αναγώγιμο (ή 1m-αναγώγιμοαναγώγιμη) στο Β, αν υπάρχει μια συνολικήσυνολικά υπολογίσιμη [[Συνάρτηση|αμφιμονοσήμαντη συνάρτηση]], τέτοιαέτσι ώστε κάθε n είναιανήκει στηνστο ΑA αν και μόνο αν το f(n) είναι στο Β.
;Αναγωγισιμότητα του Πίνακα Αληθείας: Το Α είναι αληθινά αναγώγιμο σε πίνακα Β,αν το Α είναι αναγώγιμο κατά Turing στο Β μέσω της μηχανής Turing που υπολογίζει μια συνολική συνάρτηση. Λόγω του συμπαγούς του [[Χώρου Cantor|Cantor χώρου]] , αυτό είναι ισοδύναμο με το να πούμε ότι η μείωση παρουσιάζει έναν ενιαίο κατάλογο ερωτήσεων (εξαρτώμενο μόνο από την είσοδο) στο oracle ταυτόχρονα, και στη συνέχεια, έχοντας δει τις απαντήσεις τους είναι σε θέση να παράγει ένα αποτέλεσμα χωρίς να ζητήσει πρόσθετες ερωτήσεις,ανεξάρτητα με την απάντησης του oracle των αρχικών ερωτημάτων. Πολλές παραλλαγές του πίνακα αληθινής αναγωγής έχουν επίσης μελετηθεί.
 
Περαιτέρω αναγωγές(θετική,διαζευκτική,συνδετική,γραμμική και οι αδύναμες και δυνατές μορφές τους) συζητούνται στο άρθρο [[Μείωση (θεωρία αναδρομής)]] .
===== '''[[Πολλές προς μία αναγωγισιμότητα]]''' =====
Αυτό είναι ουσιαστικά η αναγωγή ένα προς ένα χωρίς τον περιορισμό ότι το f είναι αμφιμονοσήμαντο. Το Α είναι πολλοί προς ένα αναγώγιμο (ή m-αναγώγιμη) στο Β, αν υπάρχει μια συνολικά υπολογίσιμη συνάρτηση, έτσι ώστε κάθε n ανήκει στο A αν και μόνο αν το f(n) είναι στο Β.
 
===== '''[[Αναγωγισιμότητα του Πίνακα Αληθείας]]''' =====
Το Α είναι αληθινά αναγώγιμο σε πίνακα Β,αν το Α είναι αναγώγιμο κατά Turing στο Β μέσω της μηχανής Turing που υπολογίζει μια συνολική συνάρτηση. Λόγω του συμπαγούς του [[Χώρου Cantor|Cantor χώρου]] , αυτό είναι ισοδύναμο με το να πούμε ότι η μείωση παρουσιάζει έναν ενιαίο κατάλογο ερωτήσεων (εξαρτώμενο μόνο από την είσοδο) στο oracle ταυτόχρονα,και στη συνέχεια, έχοντας δει τις απαντήσεις τους είναι σε θέση να παράγει ένα αποτέλεσμα χωρίς να ζητήσει πρόσθετες ερωτήσεις,ανεξάρτητα με την απάντησης του oracle των αρχικών ερωτημάτων. Πολλές παραλλαγές του πίνακα αληθινής αναγωγής έχουν επίσης μελετηθεί.
 
Περαιτέρω αναγωγές(θετική,διαζευκτική,συνδετική,γραμμική και οι αδύναμες και δυνατές μορφές τους) συζητούνται στο άρθρο [[Μείωση (θεωρία αναδρομής)]] .
 
Η μεγάλη έρευνα για ισχυρές αναγωγές έγινε για να συγκρίνουν τις θεωρίες τους, τόσο για την κλάση όλων των αναδρομικά αριθμήσιμων συνόλων, καθώς και για την τάξη όλων των υποσυνόλων των φυσικών αριθμών. Επιπλέον, οι σχέσεις μεταξύ των αναγωγών έχει μελετηθεί. Για παράδειγμα, είναι γνωστό ότι κάθε βαθμός Turing είναι είτε ένας βαθμός από αληθινό πίνακα ή είναι η ένωση των απείρων πολλών βαθμών από αληθινούς πίνακες.
Οι αναγωγές που είναι ασθενέστερες από ότι η αναγωγή του Turing (δηλαδή, αναγωγές που υπονοούνται από την αναγωγή του Turing) έχουν επίσης μελετηθεί.Οι πιο γνωστές είναι [[αριθμητική αναγωγή|αριθμητικές αναγωγές]] και [[υπεραριθμητική αναγωγή]].Αυτές οι αναγωγές συνδέονται στενά με την οριστικοποίηση πάνω από το καθιερωμένο μοντέλο της αριθμητικής.
 
===== '''Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία''' =====
Ο Ράις έδειξε ότι για κάθε μη τετριμμένη κατηγορία 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.
Κύριο άρθρο: [[Αντίστροφα μαθηματικά]]
 
Το πρόγραμμα των [[αντιστρόφων Μαθηματικών]] ρωτά ποια αξιώματα υπαρκτά από τα σύνολα είναι αναγκαία για να αποδειχθεί συγκεκριμένα θεωρήματα των μαθηματικών σε υποσυστήματα της [[αριθμητική δεύτερη τάξη|αριθμητικής της δεύτερης τάξης]].Η μελέτη αυτή ξεκίνησε από τον [[Harvey Friedman]] και μελετήθηκε λεπτομερώς από τον Stephen Simpson και άλλους.Ο Simpson (1999) δίνει μια λεπτομερή συζήτηση για το πρόγραμμα.Τα αξιώματα της ύπαρξης των συνόλων υπό ερώτηση αντιστοιχούν ανεπίσημα σε αξιώματα που λένε ότι το δυναμοσύνολο των ακέραιων αριθμών είναι κλειστό υπό διάφορες έννοιες αναγωγής.Το πιο αδύναμο τέτοιο αξίωμα που έχει μελετηθεί σε αντίστροφα μαθηματικά είναι η αναδρομική κατανόηση,η οποία αναφέρει ότι το δυναμοσύνολο των ακεραίων είναι κλειστό υπό την αναγωγή Turing.
 
===== '''Αρίθμηση''' =====
Η αρίθμηση είναι μια απαρίθμηση των συναρτήσεων.Έχει δύο παραμέτρους,e και χ και εξάγει την τιμή της συνάρτησης e στην αρίθμηση για την είσοδο x. Οι αριθμήσεις μπορεί να είναι μερικά-αναγώγιμες αν και ορισμένα από τα μέλη τους είναι συνολικά αναγώγιμα, δηλαδή, υπολογίσιμες συναρτήσεις.[[Παραδεκτές αριθμήσεις]] είναι εκείνες στις οποίες όλες οι άλλες μπορούν να μεταφραστούν.Μια[[Friedberg| αρίθμηση Friedberg]] (που ονομάζεται από αυτόν που την ανακάλυψε)είναι η ένα προς ένα αρίθμηση όλων των επιμέρους-αναδρομικών συναρτήσεων,είναι κατ 'ανάγκην μια μη παραδεκτή αρίθμηση.Μεταγενέστερη έρευνα ασχολήθηκε επίσης με αριθμήσεις από άλλες κατηγορίες όπως τις τάξεις των αναδρομικά αριθμήσιμων συνόλων. Ο Goncharov ανακάλυψε για παράδειγμα μια κατηγορία αναδρομικά αριθμήσιμων συνόλων για τα οποία οι αριθμήσεις εμπίπτουν σε δύο κατηγορίες ακριβώς σε σχέση με τους αναδρομικούς ισομορφισμούς.
 
'''=== Η μέθοδος της Προτεραιότητας''' ===
 
Για περαιτέρω επεξήγηση, βλ. την ενότητα [[πρόβλημα δημοσίευση και τη μέθοδο προτεραιότητας]] στο άρθρο [[βαθμός Turing]].
 
Το πρόβλημα του Post λύθηκε με μια μέθοδο που ονομάζεται η μέθοδος κατά προτεραιότητας,μια απόδειξη χρήση αυτής της μεθόδου ονομάζεται επιχείρημα προτεραιότητας.Αυτή η μέθοδος χρησιμοποιείται κυρίως για την κατασκευή αναδρομικά αριθμήσιμων συνόλων με συγκεκριμένες ιδιότητες.Για να χρησιμοποιηθεί αυτή η μέθοδος,οι επιθυμητές ιδιότητες του συνόλου που πρόκειται να κατασκευαστεί χωρίστηκαν σε έναν άπειρο κατάλογο των στόχων,που είναι γνωστός ως απαιτήσεις, έτσι ώστε ικανοποιώντας όλες τις απαιτήσεις θα κάνει το κατσκευασμένο σύνολο να έχει τις επιθυμητές ιδιότητες.Κάθε απαίτηση έχει εκχωρηθεί σε ένα φυσικό αριθμό που αντιπροσωπεύει την προτεραιότητα της απαίτησης, έτσι το 0 αποδίδεται στην πιο σημαντική προτεραιότητα,το 1 στη δεύτερη πιο σημαντική,και ούτω καθεξής.Το σύνολο στη συνέχεια κατασκευάζεται σε στάδια, σε κάθε στάδιο προσπαθεί να ικανοποιήσει μία ή περισσότερες από τις απαιτήσεις, είτε με την προσθήκη αριθμών στο σύνολο ή με την απαγόρευση των αριθμών από το σύνολο, έτσι ώστε το τελικό σύνολο να ικανοποιεί την απαίτηση.Μπορεί να συμβεί να ικανοποιείται μία απαίτηση και αυτό να προκαλεί τη μη ικανοποίηση μιας άλλης,η σειρά προτεραιότητας χρησιμοποιείται για να αποφασιστεί τι πρέπει να γίνει σε μια τέτοια περίπτωση.
Τα επιχειρήματα Προτεραιότητας έχουν χρησιμοποιηθεί για να λύσουν πολλά προβλήματα στη θεωρία αναδρομής, και έχουν ταξινομηθεί σε μια ιεραρχία με βάση την πολυπλοκότητά τους (Soare 1987).Επειδή τα περίπλοκα επιχειρήματα προτεραιότητας μπορεί να είναι τεχνικά και δύσκολα να ακολουθηθούν, παραδοσιακά θεωρείται σκόπιμο να αποδειχτούν τα αποτελέσματα χωρίς επιχειρήματα προτεραιότητας, ή να διαπιστώσουμε αν τα αποτελέσματα που αποδείχθηκαν με επιχειρήματα προτεραιότητας μπορούν επίσης να αποδειχθούν χωρίς αυτά.Για παράδειγμα, ο Kummer δημοσίευσε ένα έγγραφο σε μια απόδειξη για την ύπαρξη της αρίθμηση του Friedberg χωρίς τη χρήση της μεθόδου προτεραιότητας.
 
 
=== Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων ===
Όταν ο Post όρισε την έννοια ενός απλού συνόλου, ως ενός εκ νέου συνόλου με ένα άπειρο συμπλήρωμα που δεν περιέχει κανένα άπειρο σύνολο re, άρχισε τη μελέτη της δομής των αναδρομικά αριθμήσιμων συνόλων υπό ένταξη. Αυτό το πλέγμα έγινε μια καλά μελετημένη δομή. Αναδρομικά σύνολα μπορούν να οριστούν σε αυτή τη δομή από τη βασικό αποτέλεσμα ότι ένα σύνολο είναι αναδρομικό αν και μόνο αν το σύνολο και το συμπλήρωμά του είναι αναδρομικά αριθμήσιμα. Άπειρα σύνολα έχουν πάντα άπειρα αναδρομικά υποσύνολα αλλά από την άλλη πλευρά, υπάρχουν απλά σύνολα που υπάρχουν, αλλά δεν έχουν αναδρομικό υπερσύνολο. Ο Post (1944) εισήγαγε ήδη υπεραπλά και υπερυπεραπλά σύνολα. Αργότερα μέγιστα σύνολα κατασκευάστηκαν τα οποία είναι σύνολα τέτοια ώστε κάθε υπερσύνολο είναι είτε ένα πεπερασμένο παραλλαγή του συγκεκριμένου μέγιστου συνόλου ή συν-πεπερασμένο. Το αρχικό κίνητρο του Post στη μελέτη αυτού του πλέγματος ήταν να βρεθεί μια δομική αντίληψη, έτσι ώστε κάθε σύνολο που ικανοποιεί αυτή την ιδιότητα δεν είναι ούτε στο βαθμό Turing των αναδρομικών συνόλων ούτε στο βαθμό Turing του προβλήματος τερματισμού. Ο Post δεν κατάφερε να βρει τον εν λόγω κώδικα και η λύση στο πρόβλημά του εφαρμόστηκε στις μεθόδους προτεραιότητας. Ο Harrington και ο Soare (1991), βρήκαν τελικά ένα τέτοιο κώδικα.
 
=== Προβλήματα Αυτομορφισμού ===
Ένα άλλο σημαντικό ζήτημα είναι η ύπαρξη αυτομορφισμών στις δομές της ανάδρομης θεωρίας . Σε μία από αυτές τις δομές, το Α είναι κάτω από Β αν και μόνο αν η διαφορά συνόλου Β - Α είναι πεπερασμένη. [[Τα Μέγιστα σύνολα]] (όπως ορίζονται στην προηγούμενη παράγραφο) έχουν την ιδιότητα ότι δεν μπορούν να είναι αυτομορφικά σε μη-μέγιστη σύνολα, δηλαδή, εάν υπάρχει ένας αυτομορφισμός των αναδρομικών αριθμητικών συνόλων σύμφωνα με τη δομή που μόλις ανεφέρθη, τότε κάθε μέγιστο σύνολο αντιστοιχίζεται σε ένα άλλο μέγιστο σύνολο. Ο Soare (1974) έδειξε ότι και το αντίστροφο ισχύει, δηλαδή, κάθε δύο μέγιστα σύνολα είναι αυτόμορφα. Έτσι, τα μέγιστα σύνολα σχηματίζουν μια τροχιά, δηλαδή, κάθε αυτομορφία διατηρεί μεγιστοποίηση και οποιαδήποτε δύο μέγιστα σύνολα μετασχηματίζονται το ένα στο άλλο από κάποια αυτομορφία. Ο Harrington έδωσε ένα ακόμη παράδειγμα μιας αυτομορφικής ιδιότητας : αυτής των δημιουργικών συνόλων, των συνόλων που έχουν πολλά-ένα ισοδύναμα με το πρόβλημα τερματισμού.
 
=== Πολυπλοκότητα του Kolmogorov ===
Το πεδίο της [[πολυπλοκότητας του Kolmogorov]] και της [[αλγοριθμικής τυχαιότητας]] αναπτύχθηκε κατά τη διάρκεια του 1960 και του 1970 από τους Chaitin, Kolmogorov, Levin, Martin-Löf και Σολομόνοφ (τα ονόματα δίνονται εδώ με αλφαβητική σειρά, μεγάλο μέρος της έρευνας ήταν ανεξάρτητη, και η ενότητα της έννοιας της τυχαιότητας δεν ήταν κατανοητή εκείνη τη στιγμή). Η κύρια ιδέα είναι να εξετάσει μια [[καθολική μηχανή Turing]] U και να μετρήσει την πολυπλοκότητα ενός αριθμού (ή string) x ως το μήκος της συντομότερης p εισόδου έτσι ώστε U (p) να έχει αποτέλεσμα x .Αυτή η προσέγγιση έφερε την επανάσταση στους τρόπους που καθορίζουν πότε μια άπειρη ακολουθία (ισοδύναμα, χαρακτηριστική συνάρτηση ενός υποσυνόλου των φυσικών αριθμών) είναι τυχαία ή όχι με την επίκληση της έννοια της τυχαιότητας για πεπερασμένα αντικείμενα. Η πολυπλοκότητα του Kolmogorov όχι μόνο έγινε αντικείμενο ανεξάρτητης μελέτης, αλλά εφαρμόζεται επίσης σε άλλα θέματα, όπως σε ένα εργαλείο για τη λήψη αποδείξεων. Υπάρχουν ακόμα πολλά ανοιχτά προβλήματα σε αυτόν τον τομέα. Για το λόγο αυτό, ένα πρόσφατο συνέδριο της έρευνας στον τομέα αυτό πραγματοποιήθηκε τον Ιανουάριο του 2007 και μια λίστα των ανοικτών προβλημάτων διατηρείται από τον Joseph Miller και τον Andre Nies.
Κύριο άρθρο: [[Kolmogorov πολυπλοκότητα]]
 
Το πεδίο της [[πολυπλοκότητας του Kolmogorov]] και της [[αλγοριθμικής τυχαιότητας]] αναπτύχθηκε κατά τη διάρκεια του 1960 και του 1970 από τους Chaitin, Kolmogorov, Levin, Martin-Löf και Σολομόνοφ (τα ονόματα δίνονται εδώ με αλφαβητική σειρά, μεγάλο μέρος της έρευνας ήταν ανεξάρτητη, και η ενότητα της έννοιας της τυχαιότητας δεν ήταν κατανοητή εκείνη τη στιγμή). Η κύρια ιδέα είναι να εξετάσει μια [[καθολική μηχανή Turing]] U και να μετρήσει την πολυπλοκότητα ενός αριθμού (ή string) x ως το μήκος της συντομότερης p εισόδου έτσι ώστε U (p) να έχει αποτέλεσμα x .Αυτή η προσέγγιση έφερε την επανάσταση στους τρόπους που καθορίζουν πότε μια άπειρη ακολουθία (ισοδύναμα, χαρακτηριστική συνάρτηση ενός υποσυνόλου των φυσικών αριθμών) είναι τυχαία ή όχι με την επίκληση της έννοια της τυχαιότητας για πεπερασμένα αντικείμενα. Η πολυπλοκότητα του Kolmogorov όχι μόνο έγινε αντικείμενο ανεξάρτητης μελέτης, αλλά εφαρμόζεται επίσης σε άλλα θέματα, όπως σε ένα εργαλείο για τη λήψη αποδείξεων. Υπάρχουν ακόμα πολλά ανοιχτά προβλήματα σε αυτόν τον τομέα. Για το λόγο αυτό, ένα πρόσφατο συνέδριο της έρευνας στον τομέα αυτό πραγματοποιήθηκε τον Ιανουάριο του 2007 και μια λίστα των ανοικτών προβλημάτων διατηρείται από τον Joseph Miller και τον Andre Nies.
=== Συχνότητα υπολογισμού ===
Αυτός ο κλάδος της θεωρίας της αναδρομής ανέλυσε την ακόλουθη ερώτηση: Για σταθερά ''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 αλλά να αφήνουν έξω τουλάχιστον μια ψεύτικη.
=== Επαγωγικά Συμπεράσματα ===
Αυτή είναι το ανάδρομο θεωρητικό παρακλάδι της θεωρίας της μάθησης. Βασίζεται στο μοντέλο της μάθησης στο όριο του Gold από το 1967 και έχει εξελιχθεί έκτοτε σε όλο και περισσότερα μοντέλα της μάθησης. Το γενικό σενάριο είναι το εξής: Λαμβάνοντας υπόψη μια κατηγορία S των υπολογίσιμων συναρτήσεων, είναι ένας μαθητής (δηλαδή, αναδρομική λειτουργία) το οποίο εξάγει για κάθε είσοδο της μορφής (f (0), f (1), ..., f (n)) μια υπόθεση. Ένας μαθητής Μ μαθαίνει μια συνάρτηση f αν και σχεδόν όλες τις υποθέσεις είναι ο ίδιος δείκτης ε της f σε σχέση με προηγούμενη συμφωνία για την αποδεκτή αρίθμηση όλων των υπολογίσιμων συναρτήσεων. Ο M μαθαίνει το S αν ο M μαθαίνει κάθε f στο S. Τα βασικά συμπεράσματα είναι ότι όλες οι αναδρομικά αριθμήμενες τάξεις των συναρτήσεων μπορούν να κατακτηθούν γνωστικά, ενώ η κατηγορία REC όλων των υπολογίσιμων συναρτήσεων δεν μπορεί να κατακτηθεί. Πολλά σχετικά μοντέλα έχουν εξεταστεί και η εκμάθηση των κατηγοριών των αναδρομικά αριθμήσιμων συνόλων από τα θετικά αποθυκευμένα στοιχεία είναι ένα θέμα που μελετήθηκε από την πρωτοποριακή εργασία του Gold απο το 1967 και μετά.
 
 
=== Γενικεύσεις της υπολογισιμότητας Turing ===
Η ανάδρομη θεωρία περιλαμβάνει τη μελέτη των γενικευμένων εννοιών του τομέα αυτού, όπως η [[αριθμητική αναγωγή]] , η [[υπεραριθμιτική αναγωγή]] και [[θεωρία της α-αναδρομής]] , όπως περιγράφεται από τον Sacks (1990). Αυτές οι γενικευμένες έννοιες περιλαμβάνουν αναγωγές που δεν μπορούν να εκτελεστούν από μηχανές Turing, αλλά είναι παρ 'όλα αυτά φυσικά γενικεύσεις της αναγωγής του Turing . Οι μελέτες αυτές περιλαμβάνουν προσεγγίσεις για τη διερεύνηση της [[αναλυτικής ιεραρχίας]] η οποία διαφέρει από την [[αριθμητική ιεραρχία]] επιτρέποντας την ποσοτικοποίηση πάνω σε σύνολα των ακεραίων αριθμών εκτός από την ποσοτικοποίηση των ατομικών αριθμών. Οι περιοχές αυτές συνδέονται με τις θεωρίες των καλώς διεταγμένων και τις γραφικές αναπαραστάσεις. Για παράδειγμα, το σύνολο όλων των δεικτών των αναδρομικών (μη δυαδικές) αναπαραστάσεων χωρίς άπειρα κλαδιά είναι πλήρης για το επίπεδο της αναλυτικής ιεραρχίας. Τόσο η αναγωγιμότητα Turing και η υπεραριθμιτική αναγωγή είναι σημαντική στον τομέα της [[αποτελεσματικής περιγραφικής θεωρίας]] του σύνολο . Η ακόμα πιο γενική έννοια των [[βαθμών Κατασκευασιμότητας]] έχει μελετηθεί σε [[θεωρία συνόλων]] .
 
 
=== Συνεχής θεωρία υπολογισιμότητας ===
Η κύρια επαγγελματική οργάνωση για τη θεωρία της αναδρομής είναι [[η Ένωση της Συμβολικής Λογικής]] , η οποία οργανώνει διάφορα ερευνητικά συνέδρια κάθε χρόνο. Η διεπιστημονική ερευνητική οργάνωση [[Υπολογισιμότητα στην Ευρώπη]] (CiE) διοργανώνει επίσης μια σειρά ετήσιων συνεδρίων. Το συνέδριο CiE 2012 ήταν η διάσκεψη εκατονταετίας [[Turing]] , που πραγματοποιήθηκε στο Cambridge, στο πλαίσιο του [[έτους Alan Turing|έτους Alan Turing.]]
 
== Σημειώσεις ==
= Δείτε επίσης =
* [[Αναδρομή (επιστήμη υπολογιστών)]]
* [[Λογική Υπολογισιμότητα]] 
* [[Transcomputational πρόβλημα]] 
 
= Σημειώσεις =
# Πολλά από αυτά τα θεμελιώδη έγγραφα συλλέγονται στο The Undecidable (1965) που εκδόθηκε από τον [[Martin Davis]].
# Το πλήρες χαρτί μπορεί επίσης να βρεθεί στις σελίδες 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).
# [[Διάσκεψη για τη Λογική, Υπολογισιμότητα και τυχαιότητα]], 10 - 13 Ιαν 2007.
# Η [[αρχική σελίδα]] του Andre Nies έχει μια λίστα από ανοικτά προβλήματα στην πολυπλοκότητα Kolmogorov.
# [[Μαθηματικές|Μαθηματικές αναζητήσεις]] για τους τίτλους όπως «υπολογίσιμα enumerable" και "c.e." δείχνουν ότι πολλές εργασίες έχουν δημοσιευθεί με αυτήν την ορολογία, καθώς και με την άλλη.
# Lance Fortnow, "[[Είναι Αναδρομική, Computable ή να αποφασισθεί;]]" 15.02.2004, πρόσβαση 09/01/2006.
 
== Επιπλέον Σύνδεσμοι ==
* <ref>{{Cite web|url = [http://www.aslonline.org/|title = Association for Symbolic Logic homepage}}</ref>[[Σύλλογος για Symbolic Logic αρχική σελίδα]]
* <ref>{{Cite web|url = [http://www.maths.leeds.ac.uk/cie/|title = Computability in Europe homepage}}</ref>[[Υπολογισιμότητα στην Ευρώπη αρχική σελίδα]]
* <ref>{{Cite web|url = [http://www.comp.nus.edu.sg/~fstephan/recursiontheory.html|title = Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes}}</ref>[[Ιστοσελίδα για Θεωρία Αναδρομής στο Μεταπτυχιακό επίπεδο με περίπου 100 σελίδες των σημειώσεων διάλεξης]]
* <ref>{{Cite web|url = [http://www.comp.nus.edu.sg/~fstephan/learning.ps|title = German language lecture notes on inductive inference}}</ref>[[Γερμανική γλώσσα σημειώσεις-διάλεξη για το επαγωγικό συμπέρασμα]]
 
[[Κατηγορία:Μαθηματική λογική]]
3.253

επεξεργασίες