Απτόητοι μετά από τρεις δεκαετίες αναζήτησης και με κάποια βοήθεια από έναν υπερυπολογιστή, οι μαθηματικοί ανακάλυψαν επιτέλους ένα νέο παράδειγμα του ειδικού ακέραιου που ονομάζεται “αριθμός Dedekind”.
Γράφει ο \\ Αστέρης Αλαμπής _Μίδας
Για 32 χρόνια, ο υπολογισμός του D(9) ήταν μια ανοιχτή πρόκληση και ήταν αμφίβολο αν θα ήταν ποτέ δυνατό να υπολογιστεί αυτός ο αριθμός, δήλωσε χαρακτηριστικά ο επιστήμονας υπολογιστών Lennart Van Hirtum, από το Πανεπιστήμιο του Paderborn στη Γερμανία.
Πρώτος περιέγραψε τους αριθμούς Dedekind ο Γερμανός μαθηματικός Richard Dedekind τον 19ο αιώνα. Οι αριθμοί σχετίζονται με λογικά προβλήματα γνωστά ως «μονότονες δυαδικές συναρτήσεις» (MBFs).
Μόνο το ένατο του είδους του, ή D(9), υπολογίζεται ότι ισούται με 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Αυτό το τέρας 42 ψηφίων ακολουθεί το 23ψήφιο D(8) που ανακαλύφθηκε το 1991.
Ενα πολυτελές κότερο φορτωμένο με μεγάλα ονόματα του διεθνούς jet set ναυάγησε ανοιχτά της Σικελίας. Εκτοτε, τα ΜΜΕ φροντίζουν να μας ενημερώνουν αναλυτικά για κάθε…
Η κατανόηση της έννοιας του αριθμού Dedekind είναι δύσκολη για τους μη μαθηματικούς, πόσο μάλλον να την επιλύσουν. Στην πραγματικότητα, οι υπολογισμοί που εμπλέκονται είναι τόσο περίπλοκοι και περιλαμβάνουν τόσο τεράστιους αριθμούς, που δεν ήταν σίγουρο ότι η D(9) θα ανακαλυπτόταν ποτέ. Στο κέντρο ενός αριθμού Dedekind βρίσκονται συναρτήσεις Boolean, ή ένα είδος λογικής που επιλέγει μια έξοδο από εισόδους που αποτελούνται από δύο μόνο καταστάσεις, όπως ένα true_false, ή 0 _1. Οι μονότονες δυαδικές συναρτήσεις είναι εκείνες που περιορίζουν τη λογική με τέτοιο τρόπο ώστε η εναλλαγή ενός 0 με ένα 1 σε μια είσοδο προκαλεί μόνο αλλαγή της εξόδου από 0 σε 1 και όχι από 1 σε 0.
Οι ερευνητές το περιγράφουν χρησιμοποιώντας κόκκινα και λευκά χρώματα αντί για 1 και 0, αλλά η ιδέα είναι η ίδια. Βασικά, μπορείτε να σκεφτείτε μια μονότονη συνάρτηση Boole σε δύο, τρεις και άπειρες διαστάσεις ως ένα παιχνίδι με έναν κύβο ν-διάστατων», ανέφερε ο Van Hirtum.
σσ. Στα Μαθηματικά και την Μαθηματική λογική, Άλγεβρα Μπουλ είναι η υποπεριοχή της άλγεβρας όπου οι τιμές των μεταβλητών είναι οι τιμές true_false, ή 0 _1 _αληθές – ψευδές, που συνήθως αναπαρίστανται με 1 και 0 αντίστοιχα. Σε αντίθεση με την στοιχειώδη άλγεβρα όπου οι τιμές των μεταβλητών είναι αριθμοί και οι κύριες πράξεις είναι η πρόσθεση και ο πολλαπλασιασμός, εδώ υπάρχουν τρεις κύριες πράξεις: η σύζευξη και (∧), η διάζευξη (∨) και η άρνηση _όχι (¬). Η άλγεβρα Μπουλ εισήχθη το 1854 από τον Τζορτζ Μπουλ (George Boole) με το έργο του An Investigation of the Laws of Thought (Διερεύνηση των νόμων της σκέψης). Σύμφωνα με τον Huntington ο όρος «Άλγεβρα Μπουλ» χρησιμοποιήθηκε για πρώτη φορά από τον Sheffer το 1913. Η άλγεβρα Μπουλ είναι θεμελιώδους σημασίας για την επιστήμη της Πληροφορικής και αποτελεί την βάση για την θεωρητική μελέτη του πεδίου της λογικής σχεδίασης. Επιπλέον είναι σημαντική σε άλλα πεδία όπως η Στατιστική, η Θεωρία συνόλων και ο προγραμματισμός.
“Εξισορροπείτε τον κύβο σε μια γωνία και μετά χρωματίζετε κάθε μία από τις υπόλοιπες γωνίες είτε λευκές είτε κόκκινες”. “Υπάρχει μόνο ένας κανόνας: δεν πρέπει ποτέ να τοποθετείτε μια λευκή γωνία πάνω από μια κόκκινη. Αυτό δημιουργεί ένα είδος κάθετης κόκκινης-λευκής διασταύρωσης. Το αντικείμενο του παιχνιδιού είναι να μετρήσετε πόσα διαφορετικά κοψίματα υπάρχουν.” Τα πρώτα είναι αρκετά απλά. Οι μαθηματικοί μετρούν το D(1) ως μόλις 2, μετά 3, 6, 20, 168…
Πίσω στο 1991, χρειάστηκε ένας υπερυπολογιστής Cray-2 (ένας από τους πιο ισχυρούς υπερυπολογιστές εκείνης της εποχής) και ο μαθηματικός Doug Wiedemann 200 ώρες για να καταλάβει τον D(8). Ο D(9) κατέληξε να είναι σχεδόν διπλάσιος από το μήκος του D(8) και απαιτούσε ένα ειδικό είδος υπερυπολογιστή: έναν που χρησιμοποιεί εξειδικευμένες μονάδες που ονομάζονται Field Programmable Gate Arrays (Πίνακες προγραμματιζόμενων πυλών πεδίου _FPGAs) που μπορούν να διατρέχουν πολλαπλούς υπολογισμούς παράλληλα. Αυτό οδήγησε την ομάδα στον υπερυπολογιστή Noctua 2 στο Πανεπιστήμιο του Paderborn.
“Η επίλυση σκληρών συνδυαστικών προβλημάτων με FPGA είναι ένα πολλά υποσχόμενο πεδίο εφαρμογής και ο Noctua 2 ένας από τους λίγους υπερυπολογιστές παγκοσμίως με τους οποίους το πείραμα είναι εφικτό”, λέει ο επιστήμονας υπολογιστών Christian Plessl, επικεφαλής του Paderborn Center for Parallel Computing (PC2 ) όπου φυλάσσεται το Noctua 2.
Απαιτήθηκαν περαιτέρω βελτιστοποιήσεις για να δώσουν στο Noctua 2 κάτι να δουλέψει. Χρησιμοποιώντας συμμετρίες στον τύπο για να κάνουν τη διαδικασία πιο αποτελεσματική, οι ερευνητές έδωσαν στον υπερυπολογιστή ένα τεράστιο ποσό για να καταλάβει, ένα άθροισμα που περιλάμβανε 5,5*10^18 όρους (ο αριθμός των κόκκων άμμου στη Γη υπολογίζεται σε 7,5*10^ 18, για σύγκριση).
Μετά από πέντε μήνες, το Noctua 2 βρήκε μια απάντηση και τώρα έχουμε D(9). Οι ερευνητές δεν έχουν κάνει καμία αναφορά στο D(10) προς το παρόν – αλλά μπορούμε να φανταστούμε ότι μπορεί να χρειαστούν άλλα 32 χρόνια για να το βρουν. Η εργασία πρωτοπαρουσιάστηκε τον Σεπτέμβριο στο Διεθνές Εργαστήριο Boolean Functions and their Applications (BFA) στη Νορβηγία και έπεται συνέχεια.
