Ο Terence Tao αποδεικνύει εικασία του Paul Erdos

Πώς τα «μολύβια» νίκησαν τους υπολογιστές

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

Το μολύβι κρατούσε ο Terence Tao

Ο Terence Tao πριν από ένα μήνα δημοσίευσε την απόδειξη μιας εικασίας του Paul Erdos, που είχε διατυπωθεί πριν από 80 χρόνια: «The Erdos discrepancy problem«

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

Η εικασία του Έρντος

Ο Τέρενς Τάο από το Πανεπιστήμιο της Καλιφόρνιας στο Λος Άντζελες δημοσίευσε μια απόδειξη για την ασυμφωνία του Έρντος, ένα πρόβλημα που αφορά τις ιδιότητες μιας άπειρης τυχαίας αλληλουχίας από +1 και -1.

O Paul Erdős, αριστερά, και ο Terence Tao συζητούν μαθηματικά προβλήματα το 1985.

O Paul Erdős, αριστερά, και ο Terence Tao συζητούν μαθηματικά προβλήματα το 1985.

Τη δεκαετία του 1930 ο Ούγγρος μαθηματικός Πολ Έρντος είχε αναρωτηθεί αν τα μοτίβα και η δομή μιας τέτοιας αλληλουχίας θα έπρεπε πάντα να βρίσκονται μέσα στην τυχαιότητα. Ένας τρόπος για να μετρηθεί αυτό είναι με τον υπολογισμό μιας τιμής η οποία είναι γνωστή ως ασυμφωνία. Κάτι τέτοιο απαιτεί την πρόσθεση όλων των +1 και -1 που περιλαμβάνονται σε κάθε δυνατή υποαλληλουχία. Ίσως νομίζετε πως όλα αυτά τα συν και πλην αλληλοακυρώνονται για να δώσουν το μηδέν, όμως ο Έρντος είχε εικάσει ότι καθώς οι υποαλληλουχίες γίνονται μεγαλύτερες το σύνολο αυτής της πρόσθεσης θα έπρεπε και αυτό να αυξάνεται. Στην πραγματικότητα είχε πει ότι η ασυμφωνία θα έπρεπε να είναι άπειρη, κάτι το οποίο σημαίνει ότι η πρόσθεση συνεχίζεται αιωνίως.

Τον περασμένο χρόνο ο Αλεξέι Λισίτσα και ο Μπορίς Κόνοφ από το Πανεπιστήμιο του Λίβερπουλ στη Βρετανία χρησιμοποίησαν έναν υπολογιστή για να αποδείξουν ότι η ασυμφωνία είναι πάντοτε μεγαλύτερη του δύο [A SAT Attack on the Erdos Discrepancy Conjecture]. Η απόδειξη στην οποία κατέληξαν είχε όγκο 13 gigabytes – περίπου όσο όλα μαζί τα κείμενα της Wikipedia – και κανένας άνθρωπος δεν θα μπορούσε ούτε καν να ελπίζει ότι θα την ελέγξει.

Άνθρωπος – αλγόριθμος=1-0
Ο Τέρενς Τάο με τη βοήθεια του πληθοπορισμού χρησιμοποίησε πιο παραδοσιακά μαθηματικά για να αποδείξει ότι ο Ερντος είχε δίκιο: η ασυμφωνία είναι άπειρη, όποια και αν είναι η αλληλουχία που θα επιλέξει κάποιος.
Ο κ. Λισίτσα απέδωσε τα εύσημα στον κ. Τάο για το γεγονός ότι πέτυχε αυτό που ο αλγόριθμος του ιδίου και του συνεργάτη του δεν κατόρθωσε να κάνει. «Αυτό είναι ένα χαρακτηριστικό παράδειγμα υψηλής ποιότητας ανθρώπινων μαθηματικών» δήλωσε. Παρ’ όλα αυτά οι μαθηματικοί καταφεύγουν όλο και περισσότερο στις μηχανές για βοήθεια, τάση η οποία αναμένεται να συνεχιστεί στο μέλλον.
tovima.gr

Διαβάστε περισσότερα:
1. Maths whizz solves a master’s riddle
2. A Magical Answer to an 80-Year-Old Puzzle
3. A Mathematical Proof Too Long To Check – The Erdos Discrepancy Conjecture



Κατηγορίες:ΜΑΘΗΜΑΤΙΚΑ

Ετικέτες: ,

Σχολιάστε

Ο ιστότοπος χρησιμοποιεί το Akismet για την εξάλειψη των ανεπιθύμητων σχολίων. Μάθετε πως επεξεργάζονται τα δεδομένα των σχολίων σας.