ΤΟ ΔΕΚΑΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ HILBERT

Πρόλογος του συγγραφέα στην ελληνική έκδοση 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