Βασική θεωρία υπολογισιμότητας

Ενα πρόβλημα είναι μηχανικά επιλύσιμο, ή υπολογίσιμο (computable), αν μπορεί να επιλυθεί από μια μηχανή, κατάλληλα διαμορφωμένη ώστε να μπορεί να δεχθεί ως είσοδο τα δεδομένα και να μπορεί να εκτελέσει απλές ενέργειες για την υλοποίηση κάποιου αλγόριθμου υπολογισμού. Η έννοια αυτή του “υπολογίσιμου” παραμένει ωστόσο ασαφής και διαισθητική, τουλάχιστο μέχρι να μπορέσουμε να περιγράψουμε μια αφηρημένη μηχανή, η οποία να έχει την επιθυμητή συμπεριφορά, όπως αυτή σκιαγραφήθηκε παραπάνω. Η αυστηρή περιγραφή μιας κατάλληλης αφηρημένης μηχανής έχει σημαντική σημασία, εφόσον διαθέτοντας μια σαφή, μαθηματική έννοια αφηρημένης μηχανής, διαθέτουμε πλέον και ένα σαφές, μαθηματικό κριτήριο σχετικά με το τι είναι και τι δεν είναι (μηχανικά) υπολογίσιμο. Στην κατεύθυνση της αυστηρής περιγραφής μιας αφηρημένης μηχανής κινήθηκε πρώτος ο Βρετανός logician Alan Turing. Οι αφηρημένες μηχανές που περιέγραψε είναι σήμερα πλέον γνωστές ως Μηχανές Turing (Turing Machines) και αποτελούν το αντικείμενο του πρώτου Κεφαλαίου.
Μπορούμε όμως να παρατηρήσουμε επίσης ότι, από μαθηματική άποψη, ένας αλγόριθμος μπορεί να θεωρηθεί ως μια συνάρτηση με πεδίο ορισμού το σύνολο του είδους δεδομένων στα οποία εφαρμόζεται και πεδίο τιμών το σύνολο του είδους δεδομένων τα οποία παράγει. Οι αλγόριθμοι που μας ενδιαφέρουν είναι κατά κανόνα αλγόριθμοι από συμβολοσειρές σε συμβολοσειρές, ή από φυσικούς αριθμούς σε φυσικούς αριθμούς. Παίρνοντας υπόψη μας τη δυνατότητα αριθμητικοποίησης, καταλήγουμε ότι, χωρίς βλάβη της γενικότητας, μπορούμε να θεωρήσουμε μόνον αλγόριθμους που υποδηλώνονται από συναρτήσεις στους φυσικούς αριθμούς. Συμπεραίνουμε ότι, η έννοια του (μηχανικά, αλγοριθμικά) υπολογίσιμου μπορεί επίσης να διευκρινιστεί, αν σταθεί δυνατό να περιγράψουμε με σαφήνεια την κλάση των συναρτήσεων τις οποίες θεωρούμε διαισθητικά ότι εκφράζουν αλγορίθμους. Στην κατεύθυνση αυτή του καθορισμού της έννοιας του υπολογίσιμου κινήθηκε αρχικά ο Goedel, με αποτέλεσμα στη συνέχεια να καθορισθεί, χάρη στη σημαντική συνεισφορά του Kleene, η κλάση των συναρτήσεων που είναι σήμερα γνωστές ως μερικές αναδρομικές συναρτήσεις.
Στο δεύτερο και τρίτο Κεφάλαιο αυτής της μονογραφίας εξετάζουμε αναλυτικά τις Μηχανές Turing και τις Αναδρομικές Συναρτήσεις και δίνουμε (τη δική μας εκδοχή) της κλασικής πλέον απόδειξης για την ισοδυναμία των δύο αυτών μοντέλων υπολογισιμότητας. Επιπλέον, έχοντας μια αυστηρή περιγραφή της έννοιας του υπολογίσιμου, θα διαπιστώσουμε στο τελευταίο Κεφάλαιο ότι υπάρχουν συγκεκριμένα προβλήματα τα οποία είναι αλγοριθμικά ανεπιλύσιμα, τα οποία δηλαδή δεν είναι δυνατό να επιλυθούν από μια Μηχανή Turing. Με άλλα λόγια, υπάρχουν ερωτήματα τα οποία δεν είναι μηχανικά αποφασίσιμα (decidable). Η μονογραφία αυτή απευθύνεται σε προπτυχιακούς φοιτητές και για το λόγο αυτό έγινε κάθε προσπάθεια από το συγγραφέα να παρουσιαστεί το γενικά θεωρούμενο ως δύσκολο αντικείμενο της Υπολογισιμότητας με τον απλούστερο δυνατό τρόπο.
Συνοδευτικό Software: Στο συνοδευτικό λογισμικό θα βρει ο αναγνώστης υλοποιημένες (στη Visual Turing) όλες τις μηχανές Turing που κατασκευάζονται σ’ αυτή τη μονογραφία, έτσι ώστε να μπορεί να τρέξει τις μηχανές αυτές για να διαπιστώσει στην πράξη πώς λειτουργούν.