ΤΟ ΔΕΚΑΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ HILBERT
- +
Τελική τιμή: 18,00€
Αρχική τιμή: 24,00€ Έκπτωση -25% (6,00€)
Δωρεάν έξοδα αποστολής για αγορές 30,00 και άνω
Βάρος 0,450 kg
Είδος

Έκδοση

Εκδότης

Έτος έκδοσης

ISBN

Μετάφραση

ΔΗΜΟΣΘΕΝΗΣ ΣΤΑΛΙΔΗΣ

Μήνας έκδοσης

Σελίδες

Σχήμα

Η αναζήτηση µεθόδου που επιτρέπει να αποφασίσουµε αν οποιαδήποτε διοφαντική εξίσωση επιδέχεται ή όχι
ακέραιες λύσεις ήταν το δέκατο από τα 23 προβλήµατα που ο Hilbert κληροδότησε στους µαθηµατικούς του
εικοστού αιώνα, κατά την περίφηµη διάλεξή του στο Παρίσι, το 1900. Χρειάσθηκε να περάσουν επτά
δεκαετίες έως ότου ο Γιούρι Ματιγιάσεβιτς έδωσε την οριστική και αρνητική απάντηση: µια τέτοια µέθοδος
(ή αλγόριθµος, όπως θα λέγαµε σήµερα) είναι αδύνατη.
Η απόδειξη αυτής της «αδυνατότητας» είναι το κύριο αντικείµενο του βιβλίου και συνοδεύεται από πολλές
εφαρµογές της τεχνικής που επινοήθηκε για την επίλυση του Δεκάτου Προβλήµατος.
Τονίζουµε ιδιαιτέρως την ευγενή και πολύτιµη συµµετοχή του συγγραφέα, ο οποίος συνεισέφερε διορθώσεις
και προσθήκες στην αρχική έκδοση του 1993 και, κυρίως, εκτεταµένο πρόλογο στην ελληνική έκδοση µε
ουσιαστική ενηµέρωση της βιβλιογραφίας. Ως αποτέλεσµα, το παρόν βιβλίο συνιστά, εν έτει 2022, το
πληρέστερο παγκοσµίως σύγγραµµα επί του θέµατος .

Πρόλογος του συγγραφέα στην ελληνική έκδοση v
Βιβλιογραφία προλόγου . . . . . . . . . . . . . . . . . . . . . . . . . . . x
Πρόλογος στην πρώτη έκδοση xix
Σημείωμα του μεταφραστή xxiii
1 Βασικές έννοιες 1
1.1 Οι διοφαντικές εξισώσεις ως πρόβλημα απόφασης . . . . . . . . . . 1
1.2 Συστήματα διοφαντικών εξισώσεων . . . . . . . . . . . . . . . . . 3
1.3 ȁύσεις σε φυσικούς αριθμούς . . . . . . . . . . . . . . . . . . . . 4
1.4 Διοφαντικά σύνολα . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Ορολογία της ȁογικής . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Απλά παραδείγματα διοφαντικών εννοιών . . . . . . . . . . . . . . 11
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Αναπάντητα προβλήματα . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Η εκθετική συνάρτηση είναι διοφαντική 17
2.1 Ειδικές δευτεροτάξιες αναδρομικές ακολουθίες . . . . . . . . . . . 17
2.2 Οι ειδικές αναδρομικές ακολουθίες είναι διοφαντικές (βασικές ιδέες) 19
2.3 Οι ειδικές αναδρομικές ακολουθίες είναι διοφαντικές (απόδειξη) . . 23
2.4 Η εκθετική συνάρτηση είναι διοφαντική . . . . . . . . . . . . . . . 28
2.5 Εκθετικές διοφαντικές εξισώσεις . . . . . . . . . . . . . . . . . . . 29
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Ανοικτά ερωτήματα . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Διοφαντική κωδικοποίηση 37
3.1 Αρίθμηση Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Ȁωδικοποίηση Gödel . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Kωδικοποίηση θέσης . . . . . . . . . . . . . . . . . . . . . . . . . 40
i
ii Περιεχόμενα
3.4 Διωνυμικοί συντελεστές, παραγοντικό, πρώτοι αριθμοί . . . . . . . 41
3.5 Σύγκριση πλειάδων . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6 Επεκτάσεις συναρτήσεων σε πλειάδες . . . . . . . . . . . . . . . . 45
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Ανοικτά ερωτήματα . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Καθολικές διοφαντικές εξισώσεις 51
4.1 Βασικοί ορισμοί . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Ȁωδικοποίηση εξισώσεων . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Ȁωδικοποίηση δυνατών λύσεων . . . . . . . . . . . . . . . . . . . 55
4.4 Υπολογισμός τιμών πολυωνύμων . . . . . . . . . . . . . . . . . . . 56
4.5 Ȁαθολικές διοφαντικές εξισώσεις (κατασκευή) . . . . . . . . . . . 57
4.6 Διοφαντικά σύνολα με μη διοφαντικό συμπλήρωμα . . . . . . . . . 58
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Ανοικτό ερώτημα . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Αλγοριθμική μη επιλυσιμότητα του Δεκάτου Προβλήματος 65
5.1 Ȃηχανές Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Σύνθεση μηχανών . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3 Βασικές μηχανές . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Οι μηχανές Turing αναγνωρίζουν διοφαντικά σύνολα . . . . . . . . 75
5.5 Διοφαντική προσομοίωση των μηχανών Turing . . . . . . . . . . . 77
5.6 Το Δέκατο Πρόβλημα είναι μη αποφασίσιμο από μηχανές Turing . . 83
5.7 Θέση του Church . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Φραγμένοι καθολικοί ποσοδείκτες 93
6.1 Πρώτη κατασκευή: μηχανές Turing . . . . . . . . . . . . . . . . . 93
6.2 Δεύτερη κατασκευή: κωδικοποίηση Gödel . . . . . . . . . . . . . . 94
6.3 Τρίτη κατασκευή: άθροιση . . . . . . . . . . . . . . . . . . . . . . 98
6.4 Συνδέσεις μεταξύ Ογδόου και Δεκάτου Προβλήματος του Hilbert . 105
6.5 Ακόμα μία καθολική εξίσωση . . . . . . . . . . . . . . . . . . . . 111
6.6 Ακόμα ένα διοφαντικό σύνολο με μη διοφαντικό συμπλήρωμα . . . 112
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7 Προβλήματα απόφασης στη Θεωρία Αριθμών 117
7.1 Πλήθος λύσεων διοφαντικών εξισώσεων . . . . . . . . . . . . . . . 117
7.2 Ȃη λειτουργικές εκτιμήσεις . . . . . . . . . . . . . . . . . . . . . 119
Περιεχόμενα iii
7.3 Το αντίστοιχο του Δεκάτου Προβλήματος σε ακεραίους του Gauss . 126
7.4 Ομογενείς εξισώσεις και ρητές λύσεις . . . . . . . . . . . . . . . . 133
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Ανοικτά ερωτήματα . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Αναπάντητα προβλήματα . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8 Διοφαντική πολυπλοκότητα 139
8.1 Βασικοί ορισμοί . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.2 Φράγμα πλήθους αγνώστων σε εκθετικές διοφαντικές παραστάσεις 142
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Αναπάντητο πρόβλημα . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
9 Προβλήματα απόφασης στην Ανάλυση 151
9.1 Διοφαντικοί πραγματικοί αριθμοί . . . . . . . . . . . . . . . . . . . 151
9.2 ǿσότητες, ανισότητες και ταυτότητες πραγματικών μεταβλητών . . . 154
9.3 Συστήματα συνήθων διαφορικών εξισώσεων . . . . . . . . . . . . 159
9.4 Ολοκληρωσιμότητα . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
10 Άλλες εφαρμογές των διοφαντικών παραστάσεων 165
10.1 Διοφαντικά παίγνια . . . . . . . . . . . . . . . . . . . . . . . . . . 165
10.2 Γενικευμένοι ίπποι σε πολυδιάστατη σκακιέρα . . . . . . . . . . . 168
Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Σχόλια . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Παράρτημα 181
1 Το Θεώρημα των Τεσσάρων Τετραγώνων . . . . . . . . . . . . . . 181
2 Το Ȁινέζικο Θεώρημα των Υπολοίπων . . . . . . . . . . . . . . . . 183
3 Το Θεώρημα του Kummer . . . . . . . . . . . . . . . . . . . . . . 183
4 Άθροισμα γενικευμένης γεωμετρικής προόδου . . . . . . . . . . . . 184
Υποδείξεις για τις ασκήσεις 187
Βιβλιογραφία 201
Ευρετήριο συμβολισμών 231
Ευρετήριο ονομάτων 235
Ευρετήριο εννοιών 241