Το πρόβλημα της Συρακούσας

Ν. Λυγερός




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

Έστω  n > 1    { εάν     n Є 2Ν      :  n → n/2
                         { εάν     
n Є 2Ν+1  :  n → 3n +1 

Τότε η εικασία είναι η εξής: αν χρησιμοποιήσουμε επαγωγικά αυτόν τον ορισμό, καταλήγουμε με πεπερασμένα βήματα στον αριθμό 1. Με άλλα λόγια αν ορίσουμε τη λέξη ύψος ως τον αριθμό βημάτων για να καταλήξουμε στον αριθμό 1, τότε το ύψος πρέπει να είναι πεπερασμένο.

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

Το άλλο πρόβλημα προέρχεται από μια καινοτόμα ιδέα του John Conway, ο οποίος απέδειξε ότι αν μετατρέψουμε το πρόβλημα με τον εξής τρόπο:

Γενικεύουμε τη διαίρεση και χρησιμοποιούμε p τύπους σε συνάρτηση με το υπόλοιπο που ανήκει στο σύνολο {0, 1, 2, ..., p-1}, τότε δεν μπορούμε να αποφασίσουμε αν το πρόβλημα έχει λύση.

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

Τα πρόσφατα αποτελέσματα του Tomas Oliveira e Silva (Αύγουστος 2005) δείχνουν ότι η εικασία ισχύει για n ≤ 6 . 258, πράγμα το οποίο σημαίνει ότι δεν είμαστε σε μια εκφυλισμένη περίπτωση εικασίας αν και αυτό δεν αποτελεί βέβαια μια απόδειξη του γενικού πλαισίου.

Υπάρχει και μια άλλη αναλογική εικασία όπως η εικασία του Goldbach όμως η μεγάλη διαφορά είναι ότι σε αυτήν την περίπτωση γνωρίζουμε ένα κάτω φράγμα μετά από το οποίο η εικασία ισχύει. Για το πρόβλημα της Συρακούσας δεν έχουμε ακόμα ένα ανάλογο αποτέλεσμα. Συνεπώς η απλότητά του παραμένει πολύπλοκη.







free counters


Opus