Θεωρία υπολογισιμότητας
From Wikipedia, the free encyclopedia
Η θεωρία υπολογισιμότητας ή θεωρία αναδρομής, είναι ένας κλάδος της μαθηματικής λογικής, της πληροφορικής και της θεωρίας υπολογισμού που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού μη επιλυσιμότητας Τούρινγκ στα μέσα της δεκαετίας του 1930.
![]() |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Τα βασικά ερωτήματα που απευθύνονται από την Θεωρία Αναδρομής είναι
- «Τι σημαίνει για μια συνάρτηση, ορισμένη στους φυσικούς αριθμούς, ότι είναι υπολογίσιμη;»
και
- «Πώς μπορούν μη-υπολογίσιμες συναρτήσεις να κατηγοριοποιηθούν ιεραρχικά ανάλογα με το βαθμό μη-υπολογισιμότητας τους;».
Οι απαντήσεις σε αυτές τις ερωτήσεις οδήγησαν στην διαμόρφωση μίας πλούσιας θεωρίας η οποία απασχολεί ακόμη και σήμερα τους επιστήμονες. Το πεδίο των ερευνών αυτών έχει διευρυνθεί από τότε και πλέον περιέχει την έρευνα της γενικευμένης υπολογισιμότητας και προσδιορισιμότητας.
Είναι αξιοσημείωτο ότι η καθολική μηχανή Τούρινγκ, το κεντρικό αντικείμενο της θεωρίας υπολογισιμότητας, προηγείται και προκαθορίζει την εφεύρεση των σύγχρονων υπολογιστών. Ιστορικά, η έρευνα των αλγοριθμικά αποφασίσιμων συνόλων και υπολογίσιμων συναρτήσεων προέκυψε από διάφορα μαθηματικά προβλήματα που κατέληγαν να είναι μη-αποφασίσιμα. Υπάρχουν πολλές εφαρμογές αυτής της θεωρίας σε άλλους κλάδους των μαθηματικών που δεν επικεντρώνονται απαραίτητα στην αναποφασισιμότητα.
Στις πρώτες εφαρμογές της περιλαμβάνονταν το θεώρημα ενσωμάτωσης του Higman (Higman's embedding theorem), το οποίο συνδέει την Αναδρομική Θεωρία με την Θεωρία των Ομάδων που ήταν αποτέλεσμα των Michael O. Rabin και Anatoly Maltsev στην αλγοριθμική παρουσίαση της άλγεβρας αλλά και την αρνητική λύση του Hilbert's Tenth Problem. Οι πιο νέες εφαρμογές περιλαμβάνουν την αλγοριθμική τυχαιότητα που αποτελεί έρευνα του Theodore Allen Slaman, ο οποίος εφάρμοσε αναδρομικές-θεωρητικές μεθόδους για να επιλύσει προβλήματα Αλγεβρικής Γεωμετρίας και η νεότερη του δουλειά εστιάζεται στους κανονικούς αριθμούς για να λύσει προβλήματα της Αναλυτικής Θεωρίας Αριθμών.
Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την Θεωρία Μοντέλων και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing Οι θεωρητικοί της Αναδρομής στη μαθηματική λογική συχνά μελετούν τη θεωρία της σχετικής υπολογιστικότητας. Αυτό έρχεται σε αντίθεση με τη θεωρία της αναδρομικής ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνητικών κοινοτήτων, ωστόσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε από τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.