Από το ΒΗΜΑ, Ημ. Έκδοσης 19-01-2003

Η μαντική δύναμη των μαθηματικών

Η αμαρτία της «αλγοριθμικής τυχαιότητας» και το συγχωροχάρτι της αλγοριθμικής πολυπλοκότητας.
Με άλλα λόγια, μπορούμε να μάθουμε πότε θα γίνει ο επόμενος μεγάλος σεισμός ή ποιοι αριθμοί
θα κληρωθούν στο Extra 5; Τίποτε δεν αποκλείεται θεωρητικά. Το πρόβλημα είναι στην πράξη

Π. ΣΠΥΡΑΚΗΣ - Ι. Κ. ΣΤΑΜΑΤΙΟΥ

Τι καιρό θα κάνει αύριο; Πότε και πού θα γίνει ο επόμενος μεγάλος σεισμός; Σε ποια θέση θα βρίσκονται οι πλανήτες του ηλιακού μας συστήματος ύστερα από μία χιλιετία; Ποια θα είναι τα νούμερα στην κλήρωση του Λόττο (ή Extra αν προτιμάτε!); Αυτά είναι μερικά, μόνο, από τα ερωτήματα (άλλα πολύ κρίσιμα για τους ανθρώπους και άλλα απλώς ωφελιμιστικά!) πίσω από τα οποία βρίσκεται η μαγική λέξη «πρόβλεψη»: του καιρού, των σεισμών, των αριθμών του Λόττο! Η θεμελιώδης παραδοχή πίσω από κάθε προσπάθεια πρόβλεψης είναι ότι το φαινόμενο υπόκειται σε κάποια νομοτελειακή εξέλιξη στον χρόνο, όπου η κατάσταση στο μέλλον είναι μία (πιθανότατα πολύπλοκη) συνάρτηση της κατάστασης του φαινομένου τη στιγμή της παρατήρησης. Συνεπώς η πρόβλεψη ανάγεται στην εφαρμογή μεθόδων με στόχο την ανακάλυψη αυτής της συνάρτησης, της νομοτέλειας δηλαδή πίσω από την εξέλιξη του φαινομένου! Για παράδειγμα, η εξέλιξη των καιρικών φαινομένων μπορεί να μοντελοποιηθεί μέσα από πολύπλοκα συστήματα διαφορικών εξισώσεων, ενώ η κίνηση των πλανητών στο ηλιακό μας σύστημα υπόκειται στους νόμους κίνησης των πλανητών της κλασικής ουράνιας μηχανικής.

Οι πρόδρομοι του Χάους
Το ζήτημα εάν η εξέλιξη του κόσμου μας μοιάζει με το ξεκούρδισμα του μηχανισμού ενός ρολογιού, όπου το κάθε βήμα οδηγεί με μοναδικό τρόπο στο επόμενο, είναι παλιό και κινείται στα όρια μεταξύ φιλοσοφίας και επιστήμης. Η εμφάνιση της κβαντικής φυσικής γκρέμισε πολλά κάστρα του ντετερμινισμού, παρά το ότι μεγάλοι επιστήμονες, όπως ο Αϊνστάιν, δεν πιστεύουν τελικά σε έναν Θεό που «παίζει ζάρια με το Σύμπαν». Κάστρα του ντετερμινισμού είχε γκρεμίσει άλλωστε αρκετά νωρίτερα και η πανηγυρική κατάρριψη της δυνατότητας ακριβούς προσομοίωσης ενός συνόλου πολύπλοκων εξισώσεων που περιγράφουν ένα φυσικό φαινόμενο: η περίφημη απόδειξη του Henri Poincare της αδυναμίας πρόβλεψης της κίνησης ενός συνόλου ουράνιων σωμάτων, η οποία και αποτέλεσε τον πρόδρομο της Θεωρίας του Χάους.

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

Το αντιφατικό ερώτημα
Ας παραλλάξουμε τώρα λίγο το προηγούμενο ερώτημά μας: «Είναι δυνατή η εύρεση μιας μεθόδου κατασκευής πραγματικά τυχαίων φαινομένων, έστω μιας ακολουθίας δυαδικών ψηφίων που να αντιστοιχούν στο στρίψιμο ενός τίμιου νομίσματος, μέσα από μια συστηματική διαδικασία ή αλγόριθμο;». Φυσικά, διατυπωμένο με αυτόν τον τρόπο, το ερώτημα είναι αντιφατικό, πράγμα που οδήγησε τον μεγάλο John von Neumann να δηλώσει ότι «όποιος προσπαθεί να κατασκευάσει τυχαίους αριθμούς με χρήση κάποιας αλγοριθμικής μεθόδου είναι αμαρτωλός»! Ποιος όμως μίλησε για πραγματική τυχαιότητα; Εδώ δεν την είχαμε στο στρίψιμο ενός νομίσματος και στη μηχανική κληρωτίδα, γιατί να είμαστε τόσο απαιτητικοί τώρα; Η λύση βρίσκεται στην κατασκευή ψευδοτυχαίων αριθμών των οποίων το όνομα τους υποτιμά καθώς και αυτοί, τελικά, είναι σίγουρο ότι θα παιδέψουν άσχημα τον επίδοξο «μάντη»!

Οι «μονόδρομες» συναρτήσεις
Αλλάζοντας, προς στιγμήν, κλίμα το 1936 ο Alan Turing θεμελίωσε την επιστήμη των υπολογιστών με τον ορισμό της Μηχανής Turing, η οποία δεν είναι τίποτε άλλο παρά ένα (ιδανικό) μοντέλο του σύγχρονου ηλεκτρονικού υπολογιστή. Μια από τις εκπληκτικές συνέπειες της μοντελοποίησης αυτής ήταν και η, μετέπειτα, ανακάλυψη από έναν εκ των θεμελιωτών της θεωρίας της πολυπλοκότητας, τον Stephen Cook, ότι υπάρχουν προβλήματα τα οποία απαιτούν τεράστιους υπολογιστικούς πόρους (κυρίως χρόνο) για να επιλυθούν στη γενικότητά τους, κατ' αναλογίαν με την αναγκαιότητα για πολύπλοκους και εξαιρετικά ακριβείς υπολογισμούς σε μια μηχανική κληρωτίδα. Η σύγχρονη επιστήμη της κρυπτογραφίας μάς εφοδιάζει με εργαλεία για το χτίσιμο μεθόδων που, επαναλαμβανόμενες, παράγουν αριθμούς οι οποίοι δεν είναι προβλέψιμοι εκτός αν δαπανηθεί εξαιρετικά τεράστιος χρόνος με χρήση των ταχύτερων υπολογιστών που υπάρχουν σήμερα και θα υπάρξουν στο εγγύς μέλλον! Εχουμε το σχήμα RSA, βασισμένο στο πρόβλημα της παραγοντοποίησης ακεραίων, το σχήμα BBS, που στηρίζεται στην υπόθεση των τετραγωνικών υπολοίπων, σχήματα που στηρίζονται σε άλλα προβλήματα όπως αυτό της εύρεσης του διακριτού λογαρίθμου, σχήματα που χρησιμοποιούν συμβατικούς κρυπταλγόριθμους διαμοιραζόμενου κλειδιού όπως ο DES, με ταυτόχρονη χρήση και ειδικών «μονόδρομων» συναρτήσεων, μια λίστα εργαλείων δίχως τέλος! Προσθέστε σε όλα αυτά και ψηφιοποιημένο θόρυβο που λαμβάνεται από αντιστάσεις (thermal noise) και ημιαγωγά στοιχεία (thermal noise, shot noise, flicker noise) για το ξεκίνημα των παραπάνω μεθόδων (seed) και φτάσατε στην απόλυτη τυχαιότητα: η παραγόμενη ακολουθία αριθμών δεν είναι προβλέψιμη ούτε από τους ίδιους τους κατασκευαστές της ηλεκτρονικής κληρωτίδας!

Μέθοδοι και αμαρτίες
Η περιήγησή μας στον κόσμο της τυχαιότητας ήταν, ομολογουμένως, σύντομη και σίγουρα όχι αρκετά βαθιά. Αυτό όμως που θα θέλαμε να μείνει είναι ότι η εισαγωγή υπολογιστικών μεθόδων σε πεδία εφαρμογών όπου η λέξη «μέθοδος» παραπέμπει στη διάπραξη «αμαρτίας», όπως είναι τα παιγνίδια πρόβλεψης αριθμών, είναι εφικτή χάρη στη διαθεσιμότητα πλήθους μεθόδων των οποίων η εκτέλεση μπορεί να ιδωθεί ως εξέλιξη ενός πλήρως ντετερμινιστικού φαινομένου του οποίου η πρόβλεψη καθίσταται πρακτικά αδύνατη λόγω της τεράστιας υπολογιστικής ισχύος που απαιτείται ώστε να επιτευχθεί. Συνεπώς, για να κλείσουμε με κάπως χιουμοριστική διάθεση, μπορούμε να παίζουμε παιγνίδια όπως το Extra 5 και το Super 3 σίγουροι ότι η ακολουθία των (ψευδο-)τυχαίων αριθμών που παράγονται από τον υπολογιστή είναι εφάμιλλης ή και καλύτερης τυχαιότητας από τους αριθμούς που παράγονται στο «αδελφό» παιγνίδι Λόττο από τη μηχανική κληρωτίδα!

Ο κ. Παύλος Σπυράκης είναι καθηγητής του Τμήματος Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής του Πανεπιστημίου Πατρών και διευθυντής του Ερευνητικού και Ακαδημαϊκού Ινστιτούτου Τεχνολογίας Υπολογιστών.

Ο κ. Γιάννης Κ. Σταματίου είναι επίκουρος καθηγητής του Τμήματος Μαθηματικών του Πανεπιστημίου Αιγαίου, μέλος της Διαπανεπιστημιακής Ερευνητικής Ομάδας «Ασφάλεια στις Τεχνολογίες Πληροφοριών και Επικοινωνιών» (Πανεπιστήμιο Αιγαίου και Οικονομικό Πανεπιστήμιο Αθηνών) και συνεργάτης του Ερευνητικού και Ακαδημαϊκού Ινστιτούτου Τεχνολογίας Υπολογιστών.