Δέκατο πρόβλημα του Χίλμπερτ

Το δέκατο πρόβλημα του Χίλμπερτ είναι το δέκατο στον κατάλογο των μαθηματικών προβλημάτων που έθεσε ο Γερμανός μαθηματικός Ντέιβιντ Χίλμπερτ το 1900. Η πρόκληση είναι να βρεθεί ένας γενικός αλγόριθμος που, για μια δεδομένη διοφαντική εξίσωση (πολυωνυμική εξίσωση με ακέραιους συντελεστές και πεπερασμένο αριθμό αγνώστων), να αποφανθεί αν η εξίσωση έχει λύση με όλους τους αγνώστους να παίρνουν ακέραιες τιμές.

Παραδείγματος χάριν, η διοφαντική εξίσωση $3x^{2}-2xy-y^{2}z-7=0$ έχει ακέραια λύση: $x=1,\ y=2,\ z=-2$. Αντίθετα, η διοφαντική εξίσωση $x^{2}+y^{2}+1=0$ δεν έχει τέτοια λύση.

Το δέκατο πρόβλημα του Χίλμπερτ έχει λυθεί και δόθηκε αρνητική απάντηση: ένας τέτοιος γενικός αλγόριθμος δεν μπορεί να υπάρξει. Αυτό είναι το αποτέλεσμα της συνδυασμένης εργασίας των Μάρτιν Ντέιβις, Γιούρι Ματιάσεβιτς, Χίλαρι Πούτναμ και Τζούλια Ρόμπινσον που καλύπτει 21 χρόνια, με τον Ματιάσεβιτς να ολοκληρώνει το θεώρημα το 1970. Το θεώρημα είναι πλέον γνωστό ως θεώρημα του Ματιάσεβιτς ή θεώρημα MRDP (ένα αρχικό όνομα για τα επώνυμα των τεσσάρων κύριων συντελεστών της λύσης του).

Όταν όλοι οι συντελεστές και οι μεταβλητές περιορίζονται να είναι θετικοί ακέραιοι αριθμοί, το σχετικό πρόβλημα του πολυωνυμικού ελέγχου ταυτότητας γίνεται μια αποφασίσιμη (χωρίς εκθετικοποίηση) παραλλαγή του προβλήματος της άλγεβρας του Τάρσκι, που μερικές φορές συμβολίζεται ως ${\overline {HSI}}.$

Υπόβαθρο

Αρχική διατύπωση

Ο Χίλμπερτ διατύπωσε το πρόβλημα ως εξής:

Δίδεται μια διοφαντική εξίσωση με οποιονδήποτε αριθμό αγνώστων και ρητούς ακέραιους συντελεστές: Να επινοηθεί μια διαδικασία σύμφωνα με την οποία, μέσω ενός πεπερασμένου αριθμού πράξεων, μπορούμε να διακρίνουμε αν η εξίσωση είναι επιλύσιμη σε ρητούς ακέραιους αριθμούς.

Οι λέξεις «διαδικασία» και «πεπερασμένος αριθμός πράξεων» έχουν ερμηνευθεί ότι ο Χίλμπερτ αναζητούσε έναν αλγόριθμο. Ο όρος «ορθολογικό ολοκλήρωμα» αναφέρεται απλώς στους ακέραιους αριθμούς, θετικούς, αρνητικούς ή μηδενικούς: 0, ±1, ±2, ... . Έτσι, ο Χίλμπερτ ζητούσε έναν γενικό αλγόριθμο για να αποφασίσει αν μια δεδομένη πολυωνυμική διοφαντική εξίσωση με ακέραιους συντελεστές έχει λύση σε ακέραιους αριθμούς.

Το πρόβλημα του Χίλμπερτ δεν αφορά την εύρεση των λύσεων. Διερωτάται μόνο αν, γενικά, μπορούμε να αποφασίσουμε αν υπάρχουν μία ή περισσότερες λύσεις. Η απάντηση σε αυτό το ερώτημα είναι αρνητική, με την έννοια ότι δεν μπορεί να επινοηθεί καμία «διαδικασία» για την απάντηση αυτού του ερωτήματος. Με σύγχρονους όρους, το 10ο πρόβλημα του Χίλμπερτ είναι ένα μη αποφασίσιμο πρόβλημα.

Διοφαντικά σύνολα

Σε μια διοφαντική εξίσωση, υπάρχουν δύο είδη μεταβλητών: οι παράμετροι και οι άγνωστοι. Το διοφαντικό σύνολο αποτελείται από τις αναθέσεις παραμέτρων για τις οποίες η διοφαντική εξίσωση είναι επιλύσιμη. Ένα τυπικό παράδειγμα είναι η γραμμική διοφαντική εξίσωση με δύο αγνώστους,

$a_{1}x+a_{2}y=a_{3}$,

όπου η εξίσωση είναι επιλύσιμη εάν και μόνο εάν ο μεγαλύτερος κοινός διαιρέτης $\gcd(a_{1},a_{2})$ διαιρεί ομοιόμορφα το $a_{3}$. Το σύνολο όλων των διατεταγμένων τριπλών $(a_{1},a_{2},a_{3})$ που ικανοποιούν αυτόν τον περιορισμό ονομάζεται Διοφαντικό σύνολο που ορίζεται από τη σχέση $a_{1}x+a_{2}y=a_{3}$. Με αυτούς τους όρους, το δέκατο πρόβλημα του Χίλμπερτ ζητάει να μάθει αν υπάρχει αλγόριθμος για να καθορίσει αν το Διοφαντικό σύνολο που αντιστοιχεί σε ένα αυθαίρετο πολυώνυμο είναι μη κενό.

Το πρόβλημα γίνεται γενικά κατανοητό με βάση τους φυσικούς αριθμούς (δηλαδή τους μη αρνητικούς ακεραίους) και όχι τους αυθαίρετους ακεραίους. Ωστόσο, τα δύο προβλήματα είναι ισοδύναμα: οποιοσδήποτε γενικός αλγόριθμος που μπορεί να αποφασίσει αν μια δεδομένη διοφαντική εξίσωση έχει λύση ακέραιου αριθμού μπορεί να τροποποιηθεί σε αλγόριθμο που αποφασίζει αν μια δεδομένη διοφαντική εξίσωση έχει λύση φυσικού αριθμού, και αντίστροφα. Σύμφωνα με το θεώρημα τεσσάρων τετραγώνων του Λαγκράνζ, κάθε φυσικός αριθμός είναι το άθροισμα των τετραγώνων τεσσάρων ακεραίων αριθμών, οπότε θα μπορούσαμε να ξαναγράψουμε κάθε παράμετρο με φυσική τιμή ως προς το άθροισμα των τετραγώνων τεσσάρων νέων παραμέτρων με ακέραια τιμή. Αντιστοίχως, αφού κάθε ακέραιος είναι η διαφορά δύο φυσικών αριθμών, θα μπορούσαμε να ξαναγράψουμε κάθε ακέραια παράμετρο ως τη διαφορά δύο φυσικών παραμέτρων. Επιπλέον, μπορούμε πάντα να ξαναγράψουμε ένα σύστημα ταυτόχρονων εξισώσεων $p_{1}=0,\ldots ,p_{k}=0$ (όπου κάθε $p_{i}$ είναι ένα πολυώνυμο) ως μία εξίσωση $p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0$.

Αναδρομικά απαριθμήσιμα σύνολα

Ένα αναδρομικά απαριθμήσιμο σύνολο μπορεί να χαρακτηριστεί ως ένα σύνολο για το οποίο υπάρχει ένας αλγόριθμος που τελικά θα σταματήσει όταν ένα μέλος του συνόλου παρέχεται ως είσοδος, αλλά μπορεί να συνεχίσει επ' αόριστον όταν η είσοδος είναι ένα μη μέλος. Ήταν η ανάπτυξη της θεωρίας υπολογισιμότητας (επίσης γνωστή ως θεωρία αναδρομής) που παρείχε μια ακριβή εξήγηση της διαισθητικής έννοιας της αλγοριθμικής υπολογισιμότητας, καθιστώντας έτσι την έννοια της αναδρομικής απαριθμησιμότητας απόλυτα αυστηρή. Είναι προφανές ότι τα διοφαντικά σύνολα είναι αναδρομικά απαριθμήσιμα (επίσης γνωστά ως ημι-αποφασιστικά). Αυτό οφείλεται στο γεγονός ότι μπορεί κανείς να οργανώσει όλες τις πιθανές πλειάδες τιμών των αγνώστων σε μια ακολουθία και στη συνέχεια, για μια δεδομένη τιμή της παραμέτρου (των παραμέτρων), να ελέγξει αυτές τις πλειάδες, τη μία μετά την άλλη, για να δει αν είναι λύσεις της αντίστοιχης εξίσωσης. Η μη επιλυσιμότητα του δέκατου προβλήματος του Χίλμπερτ είναι συνέπεια του εκπληκτικού γεγονότος ότι ισχύει το αντίστροφο:

Κάθε αναδρομικά απαριθμήσιμο σύνολο είναι διοφαντικό.

Το αποτέλεσμα αυτό είναι γνωστό ως θεώρημα του Ματιάσεβιτς (επειδή έδωσε το κρίσιμο βήμα που ολοκλήρωσε την απόδειξη) και ως θεώρημα MRDP (για τους Γιούρι Ματιάσεβιτς, Τζούλια Ρόμπινσον, Μάρτιν Ντέιβις και Χίλαρι Πούτναμ). Επειδή υπάρχει ένα αναδρομικά απαριθμήσιμο σύνολο που δεν είναι υπολογίσιμο, η μη επιλυσιμότητα του δέκατου προβλήματος του Χίλμπερτ είναι άμεση συνέπεια. Στην πραγματικότητα, μπορούν να ειπωθούν περισσότερα: υπάρχει ένα πολυώνυμο

$p(a,x_{1},\ldots ,x_{n})$

με ακέραιους συντελεστές έτσι ώστε το σύνολο των τιμών του $a$ για τις οποίες η εξίσωση

$p(a,x_{1},\ldots ,x_{n})=0$

έχει λύσεις σε φυσικούς αριθμούς δεν είναι υπολογίσιμη. Έτσι, όχι μόνο δεν υπάρχει κανένας γενικός αλγόριθμος για τον έλεγχο της επιλυσιμότητας των διοφαντικών εξισώσεων, αλλά δεν υπάρχει κανένας ακόμη και για αυτή την οικογένεια εξισώσεων μίας παραμέτρου.

Ιστορία

Έτος	Εκδηλώσεις
1944	Ο Εμίλ Λεόν Ποστ δηλώνει ότι το δέκατο πρόβλημα του Χίλμπερτ «απαιτεί μια απόδειξη ότι είναι άλυτο»
1949	Ο Μάρτιν Ντέιβις χρησιμοποιεί τη μέθοδο του Κουρτ Γκέντελ για την εφαρμογή του κινεζικού θεωρήματος υπολοίπου ως κόλπο κωδικοποίησης για να λάβει την κανονική του μορφή για αναδρομικά απαριθμήσιμα σύνολα: $\left\{a\mid \exists y\forall k\leqslant y\exists x_{1},\ldots ,x_{n}:p\left(a,k,y,x_{1},\ldots ,x_{n}\right)=0\right\}$ οπου $p$ είναι πολυώνυμο με ακέραιους συντελεστές. Καθαρά τυπικά, είναι μόνο ο περιορισμένος καθολικός ποσοδείκτης που εμποδίζει αυτό να είναι ένας ορισμός ενός διοφαντικού συνόλου. Χρησιμοποιώντας μια μη εποικοδομητική αλλά εύκολη απόδειξη, συμπέρανε ως επακόλουθο αυτής της κανονικής μορφής ότι το σύνολο των Διοφαντικών συνόλων δεν είναι κλειστό με συμπλήρωση, δείχνοντας ότι υπάρχει ένα Διοφαντικό σύνολο του οποίου το συμπλήρωμα δεν είναι Διοφαντικό. Εφόσον τα αναδρομικά απαριθμήσιμα σύνολα δεν είναι κλειστά ούτε με συμπλήρωση, εικάζει ότι οι δύο κατηγορίες είναι ταυτόσημες.
1950	Η Τζούλια Ρόμπινσον, αγνοώντας το έργο του Ντέιβις, ερευνά τη σύνδεση της εκθετικής συνάρτησης με το πρόβλημα και προσπαθεί να αποδείξει ότι το EXP, το σύνολο των τριπλέτων $(a,b,c)$ για το οποίο ισχύει $a=b^{c}$, είναι διοφαντικό. Χωρίς να τα καταφέρει, κάνει την ακόλουθη «υπόθεση» (που αργότερα ονομάστηκε Τζ.Ρ.): Υπάρχει ένα διοφαντικό σύνολο $D$ από ζεύγη $(a,b)$ τέτοια ώστε $(a,b)\in D\Rightarrow b<a^{a}$ και για κάθε θετικό $k,$ υπάρχει $(a,b)\in D$ τέτοιο ώστε $b>a^{k}.$ Χρησιμοποιώντας ιδιότητες της εξίσωσης του Πελ, αποδεικνύει ότι η Τζ.Ρ. συνεπάγεται ότι η EXP είναι διοφαντική, καθώς και τους διωνυμικούς συντελεστές, το παραγοντικό και τους πρώτους αριθμούς.
1959	Σε συνεργασία, οι Ντέιβις και Πούτναμ μελετούν τα «εκθετικά διοφαντικά σύνολα»: σύνολα που ορίζονται από διοφαντικές εξισώσεις στις οποίες ορισμένοι από τους εκθέτες μπορεί να είναι άγνωστοι. Χρησιμοποιώντας την κανονική μορφή του Ντέιβις σε συνδυασμό με τις μεθόδους του Ρόμπινσον και υποθέτοντας την αναπόδεικτη τότε εικασία ότι υπάρχουν αυθαίρετα μεγάλες αριθμητικές πρόοδοι που αποτελούνται από πρώτους αριθμούς, αποδεικνύουν ότι κάθε αναδρομικά απαριθμήσιμο σύνολο είναι εκθετικό διοφαντικό. Αποδεικνύουν επίσης ως επακόλουθο ότι ο Τζ.Ρ. συνεπάγεται ότι κάθε αναδρομικά απαριθμήσιμο σύνολο είναι διοφαντικό, το οποίο με τη σειρά του συνεπάγεται ότι το δέκατο πρόβλημα του Χίλμπερτ είναι άλυτο.
1960	Η Ρόμπινσον απλοποίησε την απόδειξη του αποτελέσματος για εκθετικά διοφαντικά σύνολα και το κατέστησε ανεξάρτητο από την εικασία για τους πρώτους αριθμούς, καθιστώντας το ένα τυπικό θεώρημα. Αυτό καθιστά την υπόθεση Τζ.Ρ. επαρκή συνθήκη για την αδιαλυτότητα του δέκατου προβλήματος του Χίλμπερτ. Ωστόσο, πολλοί αμφισβητούν την ορθότητα της υπόθεσης Τζ.Ρ.
1961–1969	Κατά τη διάρκεια αυτής της περιόδου, οι Ντέιβις και Πούτναμ βρίσκουν διάφορες προτάσεις που συνεπάγονται την Τζ.Ρ., και η Ρόμπινσον, έχοντας προηγουμένως δείξει ότι η Τζ.Ρ.. συνεπάγεται ότι το σύνολο των πρώτων αριθμών είναι ένα διοφαντικό σύνολο, αποδεικνύει ότι αυτό είναι μια συνθήκη αν και μόνο αν. Ο Γιούρι Ματιάσεβιτς δημοσιεύει ορισμένες αναγωγές του δέκατου προβλήματος του Χίλμπερτ.
1970	Βασιζόμενος στην πρόσφατα δημοσιευμένη εργασία του Νικολάι Βορόμπ'εβ για τους αριθμούς Φιμπονάτσι, ο Ματιάσεβιτς αποδεικνύει ότι το σύνολο $P=\{(a,b)|a>0,b=F_{2a}\},$ όπου $F_{n}$ είναι ο nth αριθμός Φιμπονάτσι, είναι διοφαντικό και παρουσιάζει εκθετική αύξηση. Ο συνδυασμός της Τζ.Ρ. με το θεώρημα ότι κάθε αναδρομικά απαριθμήσιμο σύνολο είναι εκθετικά διοφαντικό, αποδεικνύει ότι τα αναδρομικά απαριθμήσιμα σύνολα είναι διοφαντικά. Αυτό καθιστά το δέκατο πρόβλημα του Χίλμπερτ άλυτο.

Εφαρμογές

Το θεώρημα Ματιάσεβιτς/MRDP συνδέει δύο έννοιες -η μία από τη θεωρία υπολογισιμότητας, η άλλη από τη θεωρία αριθμών- και έχει μερικές εκπληκτικές συνέπειες. Ίσως η πιο εκπληκτική είναι η ύπαρξη μιας καθολικής διοφαντικής εξίσωσης:

Υπάρχει ένα πολυώνυμο $p(a,n,x_{1},\ldots ,x_{k})$ τέτοιο ώστε, δεδομένου οποιουδήποτε διοφαντικού συνόλου $S$ να υπάρχει ένας αριθμός $n_{0}$ τέτοιος ώστε

$S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.$

Αυτό ισχύει απλώς και μόνο επειδή τα διοφαντικά σύνολα, που είναι ίσα με τα αναδρομικά απαριθμήσιμα σύνολα, είναι επίσης ίσα με τις μηχανές Τούρινγκ. Είναι γνωστή ιδιότητα των μηχανών Τούρινγκ ότι υπάρχουν καθολικές μηχανές Τούρινγκ, ικανές να εκτελέσουν οποιονδήποτε αλγόριθμο.

Ο Χίλαρι Πούτναμ έχει επισημάνει ότι για κάθε διοφαντικό σύνολο $S$ θετικών ακεραίων αριθμών, υπάρχει ένα πολυώνυμο

$q(x_{0},x_{1},\ldots ,x_{n})$

έτσι ώστε το $S$ να αποτελείται ακριβώς από τους θετικούς αριθμούς μεταξύ των τιμών που παίρνει το $q$ ως οι μεταβλητές

$x_{0},x_{1},\ldots ,x_{n}$

να κυμαίνονται σε όλους τους φυσικούς αριθμούς. Αυτό μπορεί να γίνει αντιληπτό ως εξής: Αν

$p(a,y_{1},\ldots ,y_{n})=0$

παρέχει έναν διοφαντικό ορισμό του $S$, τότε αρκεί να θέσουμε

$q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].$

Επομένως, υπάρχουν, για παράδειγμα, πολυώνυμα για τα οποία το θετικό μέρος του εύρους τους είναι ακριβώς οι πρώτοι αριθμοί. (Από την άλλη πλευρά, κανένα πολυώνυμο δεν μπορεί να πάρει μόνο πρώτες τιμές.) Το ίδιο ισχύει και για άλλα αναδρομικά απαριθμήσιμα σύνολα φυσικών αριθμών: το παραγοντικό, τους διωνυμικούς συντελεστές, τους αριθμούς Φιμπονάτσι κ.λπ.

Άλλες εφαρμογές αφορούν αυτό που οι λογικολόγοι ονομάζουν προτάσεις $\Pi _{1}^{0}$ οι οποίες μερικές φορές αποκαλούνται επίσης προτάσεις τύπου Γκόλντμπαχ . Αυτές μοιάζουν με την εικασία του Γκόλντμπαχ, δηλώνοντας ότι όλοι οι φυσικοί αριθμοί διαθέτουν μια ορισμένη ιδιότητα που μπορεί να ελεγχθεί αλγοριθμικά για κάθε συγκεκριμένο αριθμό. Το θεώρημα Matiyasevich/MRDP υποδηλώνει ότι κάθε τέτοια πρόταση είναι ισοδύναμη με μια δήλωση που ισχυρίζεται ότι κάποια συγκεκριμένη διοφαντική εξίσωση δεν έχει λύσεις σε φυσικούς αριθμούς. Ένας αριθμός σημαντικών και διάσημων προβλημάτων είναι αυτής της μορφής: συγκεκριμένα, το τελευταίο θεώρημα του Φερμά, η υπόθεση Ρίμαν και το θεώρημα των τεσσάρων χρωμάτων. Επιπλέον, ο ισχυρισμός ότι συγκεκριμένα τυπικά συστήματα όπως η αριθμητική Πεάνο ή η ZFC είναι συνεπή μπορεί να εκφραστεί ως $\Pi _{1}^{0}$ προτάσεις. Η ιδέα είναι να ακολουθήσουμε τον Κουρτ Γκέντελ στην κωδικοποίηση των αποδείξεων με φυσικούς αριθμούς με τέτοιο τρόπο ώστε η ιδιότητα του να είναι ο αριθμός που αναπαριστά μια απόδειξη να είναι αλγοριθμικά ελέγξιμη.

Οι προτάσεις $\Pi _{1}^{0}$ έχουν την ειδική ιδιότητα ότι αν είναι ψευδείς, το γεγονός αυτό θα μπορεί να αποδειχθεί σε οποιοδήποτε από τα συνήθη τυπικά συστήματα. Αυτό συμβαίνει επειδή το ψεύδος ισοδυναμεί με την ύπαρξη ενός αντιπαραδείγματος που μπορεί να επαληθευτεί με απλή αριθμητική. Έτσι, αν μια πρόταση $\Pi _{1}^{0}$ είναι τέτοια ώστε ούτε αυτή ούτε η άρνησή της να είναι αποδείξιμες σε ένα από αυτά τα συστήματα, η πρόταση αυτή πρέπει να είναι αληθής.

Μια ιδιαίτερα εντυπωσιακή μορφή του θεωρήματος μη πληρότητας του Γκέντελ είναι επίσης συνέπεια του θεωρήματος Ματιάσεβιτς/MRDP:

Έστω

$p(a,x_{1},\ldots ,x_{k})=0$

παρέχει έναν διοφαντικό ορισμό ενός μη υπολογίσιμου συνόλου. Έστω $A$ ένας αλγόριθμος που εξάγει μια ακολουθία φυσικών αριθμών $n$ έτσι ώστε η αντίστοιχη εξίσωση

$p(n,x_{1},\ldots ,x_{k})=0$

δεν έχει λύσεις σε φυσικούς αριθμούς. Τότε υπάρχει ένας αριθμός $n_{0}$ που δεν εξάγεται από το $A$ ενώ στην πραγματικότητα η εξίσωση

$p(n_{0},x_{1},\ldots ,x_{k})=0$

δεν έχει λύσεις σε φυσικούς αριθμούς.

Για να δούμε ότι το θεώρημα είναι αληθές, αρκεί να παρατηρήσουμε ότι αν δεν υπήρχε τέτοιος αριθμός $n_{0}$, θα μπορούσαμε αλγοριθμικά να ελέγξουμε τη συμμετοχή ενός αριθμού $n$ σε αυτό το μη υπολογίσιμο σύνολο, εκτελώντας ταυτόχρονα τον αλγόριθμο $A$ για να δούμε αν ο $n$ είναι έξοδος, ενώ ταυτόχρονα ελέγχουμε όλα τα πιθανά $k$-σύνολα φυσικών αριθμών που αναζητούν λύση της εξίσωσης

$p(n,x_{1},\ldots ,x_{k})=0$

και μπορούμε να συνδέσουμε έναν αλγόριθμο $A$ με οποιοδήποτε από τα συνήθη τυπικά συστήματα, όπως η αριθμητική Πεάνο ή η ZFC, αφήνοντάς τον να παράγει συστηματικά συνέπειες των αξιωμάτων και στη συνέχεια να εξάγει έναν αριθμό $n$ κάθε φορά που μια πρόταση της μορφής

$\neg \exists x_{1},\ldots ,x_{k}[p(n,x_{1},\ldots ,x_{k})=0]$

παράγεται. Τότε το θεώρημα μας πληροφορεί ότι είτε αποδεικνύεται μια ψευδής δήλωση αυτής της μορφής είτε μια αληθής παραμένει αναπόδεικτη στο εν λόγω σύστημα.

Άλλα αποτελέσματα

Μπορούμε να αναφερθούμε στον βαθμό ενός διοφαντικού συνόλου ως τον μικρότερο βαθμό ενός πολυωνύμου σε μια εξίσωση που ορίζει το σύνολο αυτό. Αντίστοιχα, μπορούμε να ονομάσουμε διάσταση ενός τέτοιου συνόλου τον μικρότερο αριθμό αγνώστων σε μια εξίσωση που το ορίζει. Δεδομένης της υπάρξεως μιας καθολικής διοφαντικής εξίσωσης, είναι σαφές ότι υπάρχουν απόλυτα ανώτερα όρια και για τις δύο αυτές ποσότητες, και ο προσδιορισμός αυτών των ορίων έχει προσελκύσει μεγάλο ενδιαφέρον.

Ήδη από τη δεκαετία του 1920, ο Θόραλφ Σκόλεμ έδειξε ότι οποιαδήποτε διοφαντική εξίσωση είναι ισοδύναμη με μια εξίσωση βαθμού 4 ή μικρότερου. Το τέχνασμά του ήταν να εισάγει νέους αγνώστους μέσω εξισώσεων που τους έκαναν ίσους με το τετράγωνο ενός αγνώστου ή το γινόμενο δύο αγνώστων. Επαναλαμβάνοντας αυτή τη διαδικασία, λαμβάνουμε ένα σύστημα εξισώσεων δεύτερου βαθμού και στη συνέχεια μια εξίσωση 4ου βαθμού προσθέτοντας τα τετράγωνα. Έτσι, κάθε διοφαντικό σύνολο είναι τετριμμένα 4ου ή μικρότερου βαθμού. Δεν γνωρίζουμε αν αυτό είναι το καλύτερο δυνατό αποτέλεσμα.

Οι Τζούλια Ρόμπινσον και Γιούρι Ματιάσεβιτς έδειξαν ότι κάθε διοφαντικό σύνολο έχει διάσταση όχι μεγαλύτερη από 13. Αργότερα, ο Ματιάσεβιτς βελτίωσε τις μεθόδους τους για να δείξει ότι αρκούν 9 άγνωστοι. Αν και μπορεί κάλλιστα αυτό το αποτέλεσμα να μην είναι το καλύτερο δυνατό, δεν υπήρξε περαιτέρω πρόοδος. Άρα, συγκεκριμένα, δεν υπάρχει κανένας αλγόριθμος για τον έλεγχο της επιλυσιμότητας διοφαντικών εξισώσεων με 9 ή λιγότερους αγνώστους σε φυσικούς αριθμούς. Για την περίπτωση των λύσεων με ρητούς ακέραιους αριθμούς (όπως την είχε θέσει αρχικά ο Χίλμπερτ), το τέχνασμα των 4 τετραγώνων δείχνει ότι δεν υπάρχει αλγόριθμος για εξισώσεις με όχι περισσότερους από 36 αγνώστους. Αλλά ο Ζι Γουέι Σαν (Zhi Wei Sun) έδειξε ότι το πρόβλημα για τους ακέραιους αριθμούς είναι άλυτο ακόμη και για εξισώσεις με όχι περισσότερους από 11 αγνώστους.

Ο Μάρτιν Ντέιβις μελέτησε αλγοριθμικά ζητήματα που αφορούν τον αριθμό των λύσεων μιας διοφαντικής εξίσωσης. Το δέκατο πρόβλημα του Χίλμπερτ ρωτάει αν αυτός ο αριθμός είναι ή όχι 0. Έστω $A=\{0,1,2,3,\ldots ,\aleph _{0}\}$ και έστω $C$ ένα κατάλληλο μη κενό υποσύνολο του $A$. Ο Ντέιβις απέδειξε ότι δεν υπάρχει αλγόριθμος που να ελέγχει μια δεδομένη διοφαντική εξίσωση για να καθορίσει αν ο αριθμός των λύσεών της είναι μέλος του συνόλου $C$. Συνεπώς, δεν υπάρχει αλγόριθμος για να προσδιορίσουμε αν ο αριθμός των λύσεων μιας διοφαντικής εξίσωσης είναι πεπερασμένος, περιττός, τέλειο τετράγωνο, πρώτος αριθμός κ.λπ.

Η απόδειξη του θεωρήματος MRDP έχει επισημοποιηθεί στο Coq (λογισμικό).

Επεκτάσεις του δέκατου προβλήματος του Χίλμπερτ

Αλεξάνδρα Σλαπεντόκ (μέση) το 2003

Αν και ο Χίλμπερτ έθεσε το πρόβλημα για τους ρητούς ακέραιους αριθμούς, μπορεί εξίσου καλά να τεθεί για πολλούς δακτυλίους (ιδίως για κάθε δακτύλιο του οποίου ο αριθμός των στοιχείων είναι μετρήσιμος). Προφανή παραδείγματα είναι οι δακτύλιοι των ακεραίων των αλγεβρικών αριθμητικών σωμάτων καθώς και οι ρητοί αριθμοί.

Έχει πραγματοποιηθεί πολλή εργασία σχετικά με το δέκατο πρόβλημα του Χίλμπερτ για τους δακτυλίους ακεραίων αριθμών αλγεβρικών αριθμητικών σωμάτων. Βασιζόμενοι σε προηγούμενες εργασίες των Γιαν Ντένεφ και Λέοναρντ Λίπσιτς και χρησιμοποιώντας τη θεωρία σωμάτων κλάσεων, ο Χάρολντ Ν. Σαπίρο και η Αλεξάνδρα Σλαπεντόκ μπόρεσαν να αποδείξουν:

Το δέκατο πρόβλημα του Χίλμπερτ είναι άλυτο για τον δακτύλιο των ακεραίων οποιουδήποτε αλγεβρικού αριθμητικού σώματος του οποίου η ομάδα Γκαλουά πάνω στους ρητούς είναι αβελιανή ομάδα.

Οι Σλαπεντόκ και Θανάσης Φειδάς (ανεξάρτητα ο καθένας) κατέληξαν στο ίδιο αποτέλεσμα για αλγεβρικά αριθμητικά σώματα που δέχονται ακριβώς ένα ζεύγος μιγαδικών συζυγών ενσωματώσεων.

Το πρόβλημα για τον δακτύλιο των ακεραίων των αλγεβρικών αριθμητικών σωμάτων που δεν καλύπτονται από τα παραπάνω αποτελέσματα παραμένει ανοικτό. Ομοίως, παρά το μεγάλο ενδιαφέρον, το πρόβλημα για εξισώσεις πάνω από τους ρητούς παραμένει ανοιχτό. Ο Μπάρι Μαζούρ υπέθεσε ότι για οποιαδήποτε ποικιλία πάνω στους ρητούς, το τοπολογικό κλείσιμο πάνω στους πραγματικούς του συνόλου των λύσεων έχει μόνο πεπερασμένα πολλές συνιστώσες. Αυτή η εικασία συνεπάγεται ότι οι ακέραιοι δεν είναι διοφαντικοί πάνω στους ρητούς και έτσι, αν αυτή η εικασία είναι αληθής, μια αρνητική απάντηση στο δέκατο πρόβλημα του Χίλμπερτ θα απαιτούσε μια διαφορετική προσέγγιση από αυτή που χρησιμοποιείται για άλλους δακτυλίους.

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
• Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
• Proof of Dehn's Theorem at Everything2
• Weisstein, Eric W., "Dehn Invariant" από το MathWorld.
• Dehn Invariant at Everything2
• Ντέιβιντ Χίλμπερτ, Μαθηματικά προβλήματα, 6ο πρόβλημα, σε αγγλική μετάφραση.

Δείτε επίσης

• Μερική διαφορική εξίσωση
• Καρλ Φρίντριχ Γκάους
• Προβολικός χώρος
• Δυναμικός προγραμματισμός
• Μαθηματική ανάλυση
• Αλγεβρική γεωμετρία
• Μερική διαφορική εξίσωση
• Δευτεροβάθμια εξίσωση
• Χώρος Χίλμπερτ
• Ντάβιντ Χίλμπερτ
• Ευκλείδειος χώρος
• Θεωρία αριθμών
• Ισοσκελές τρίγωνο

Βιβλιογραφία

• Hilbert, David (1901). «Mathematische Probleme» (στα γερμανικά). Archiv der Mathematik und Physik. 3rd series 1: 44–63, 213–247. 
• Davis, Martin· Matiyasevich, Yuri· Robinson, Julia (1976). «Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution». Στο: Felix E. Browder, επιμ. Mathematical Developments Arising from Hilbert Problems. Proceedings of Symposia in Pure Mathematics. XXVIII.2. American Mathematical Society. σελίδες 323–378. ISBN 0-8218-1428-1. Zbl 0346.02026.  Reprinted in The Collected Works of Julia Robinson, en:Solomon Feferman, editor, pp. 269–378, American Mathematical Society 1996.
• Martin Davis, "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233–269; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
• Davis, Martin; Hersh, Reuben (1973). «Hilbert's 10th Problem». Scientific America 229 (5): 84–91. doi:10.1038/scientificamerican1173-84. Bibcode: 1973SciAm.229e..84D. 
• Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2–5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.
• M. Ram Murty and Brandon Fodden: "Hilbert’s Tenth Problem: An Introduction to Logic, Number Theory, and Computability", American Mathematical Society, (ISBN 978-1-4704-4399-3) (June, 2019).
• Shlapentokh, Alexandra (2007). Hilbert's tenth problem. Diophantine classes and extensions to global fields. New Mathematical Monographs. 7. Cambridge: en:Cambridge University Press. ISBN 978-0-521-83360-8. Zbl 1196.11166. 

Παραπομπές

• Shreeram Shankar Abhyankar, "Hilbert's Thirteenth Problem", Algèbre non commutative, groupes quantiques et invariants (Reims, 1995), 1–11, Sémin. Congr., 2, Soc. Math. France, Paris, 1997.
• Hilbert's Tenth Problem: a History of Mathematical Discovery
• Hilbert's Tenth Problem page!
• Zhi Wei Sun: On Hilbert's Tenth Problem and Related Topics
• Trailer for Julia Robinson and Hilbert's Tenth Problem στο YouTube

Πηγές

• Benjamin Hart Yandell (2002). The Honors Class, Hilbert's Problems and their solvers by Benjamin Hart Yandell b19510316 d20040825 [2002] {510'.9'04--dc21}. 
• «Hilbert's 23 problems | mathematics | Britannica». www.britannica.com (στα Αγγλικά). Ανακτήθηκε στις 15 Δεκεμβρίου 2024. 
• Bhatnagar, Nirdosh (21 Νοεμβρίου 2018). Mathematical Principles of the Internet, Volume 2: Mathematics. CRC Press. ISBN 978-1-351-37911-3. 
• Denef, Jan (2000). Hilbert's Tenth Problem: Relations with Arithmetic and Algebraic Geometry: Relations with Arithmetic and Algebraic Geometry : Workshop on Hilbert's Tenth Problem : Relations with Arithmetic and Algebraic Geometry, November 2-5, 1999, Ghent University, Belgium. American Mathematical Soc. ISBN 978-0-8218-2622-5. 
• Murty, M. Ram· Fodden, Brandon (9 Μαΐου 2019). Hilbert’s Tenth Problem: An Introduction to Logic, Number Theory, and Computability. American Mathematical Soc. ISBN 978-1-4704-4399-3.