32 χρόνια αναζήτησης και _με την βοήθεια ενός υπερυπολογιστή, εάλω ο “αριθμός Dedekind”

Απτό­η­τοι μετά από τρεις δεκα­ε­τί­ες ανα­ζή­τη­σης και με κάποια βοή­θεια από έναν υπε­ρυ­πο­λο­γι­στή, οι μαθη­μα­τι­κοί ανα­κά­λυ­ψαν επι­τέ­λους ένα νέο παρά­δειγ­μα του ειδι­κού ακέ­ραιου που ονο­μά­ζε­ται “αριθ­μός 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.

Η κατα­νό­η­ση της έννοιας του αριθ­μού 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. Η άλγε­βρα Μπουλ είναι θεμε­λιώ­δους σημα­σί­ας για την επι­στή­μη της Πλη­ρο­φο­ρι­κής και απο­τε­λεί την βάση για την θεω­ρη­τι­κή μελέ­τη του πεδί­ου της λογι­κής σχε­δί­α­σης. Επι­πλέ­ον είναι σημα­ντι­κή σε άλλα πεδία όπως η Στα­τι­στι­κή, η Θεω­ρία συνό­λων και ο προγραμματισμός.

Ο Richard Dedekind

“Εξι­σορ­ρο­πεί­τε τον κύβο σε μια γωνία και μετά χρω­μα­τί­ζε­τε κάθε μία από τις υπό­λοι­πες γωνί­ες είτε λευ­κές είτε κόκ­κι­νες”. “Υπάρ­χει μόνο ένας κανό­νας: δεν πρέ­πει ποτέ να τοπο­θε­τεί­τε μια λευ­κή γωνία πάνω από μια κόκ­κι­νη. Αυτό δημιουρ­γεί ένα είδος κάθε­της κόκ­κι­νης-λευ­κής δια­σταύ­ρω­σης. Το αντι­κεί­με­νο του παι­χνι­διού είναι να μετρή­σε­τε πόσα δια­φο­ρε­τι­κά κοψί­μα­τα υπάρ­χουν.” Τα πρώ­τα είναι αρκε­τά απλά. Οι μαθη­μα­τι­κοί μετρούν το 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) στη Νορ­βη­γία και έπε­ται συνέχεια.