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