Η εμφάνιση των ηλεκτρονικών υπολογιστών στο προσκήνιο και ο από τότε ολοένα μεγαλύτερος ρόλος που παίζουν στη ζωή του ανθρώπου, και στην επιστήμη ειδικότερα, έκανε την Yπολογιστική φυσικό αντικείμενο μελέτης των επιστημόνων Πληροφορικής. Ένα πρόγραμμα που εκτελείται από κάποιον υπολογιστή δεν είναι παρά ένας αλγόριθμος, εκφρασμένος σε γλώσσα αντιληπτή από το σύστημα του υπολογιστή. Έτσι, η ανάγκη να ερευνήσουμε με μαθηματικά εργαλεία τα θεωρητικά όρια ικανότητας (ή δυνατοτήτων) των υπολογιστών μεταφράζεται στην ανάγκη να μελετήσουμε τι μπορεί και τι δεν μπορεί να γίνει με αλγοριθμικές μεθόδους. Ένα βιβλίο-οδηγός για τον φοιτητή της επιστήμης υπολογιστών, αλλά και για όποιον θέλει να διερευνήσει το αν και γιατί οι υπολογιστές δίνουν ή δεν δίνουν λύσεις σε διάφορα μαθηματικά προβλήματα.
ΠΕΡΙΕΧΟΜΕΝΑ
0. ΛΙΓΗ ΛΟΓΙΚΗ
1. ΕΙΣΑΓΩΓΗ
1.1 Σύνολα
1.2 Σχέσεις και συναρτήσεις
1.3 Mερικές ειδικές σχέσεις
1.4 Aριθμήσιμα και μη αριθμήσιμα σύνολα
2. ΠΡΩΤΟΓΕΝΕΙΣ ΑΝΑΔΡΟΜΙΚΕΣ ΣΥΝΑΡΤΗΣΕΙΣ
2.1 Oρισμοί και απλά παραδείγματα
2.2 Πρωτογενή αναδρομικά κατηγορήματα
2.3 Φραγμένη αναζήτηση
2.4 Συναρτήσεις ζεύγους
2.5 Mερικά ειδικά σχήματα αναδρομής
2.6 Eπανάληψη
2.7 Mια γλώσσα προγραμματισμού για την PR
3. MΕΡΙΚΕΣ ΑΝΑΔΡΟΜΙΚΕΣ ΚΑΙ ΑΝΑΔΡΟΜΙΚΕΣ ΣΥΝΑΡΤΗΣΕΙΣ
3.1 Oρισμοί και απλά παραδείγματα
3.2 Aναδρομικά κατηγορήματα
3.3 H συνάρτηση του Ackermann
3.4 Aποτελεσματική αριθμησιμότητα
3.5 Mηχανολογία
3.6 Aριθμητικοποίηση
3.7 Θεώρημα S–m–n και συνέπειες
4. TΟ ΘΕΩΡΗΜΑ MΗ ΠΛΗΡΟΤΗΤΑΣ ΤΟΥ GODEL
4.1 Tο Πρώτο Θεώρημα Aτέλειας του Godel
4.2 Oι n I K και n I K είναι αριθμητικοί τύποι
