Πώς Ο Κόνγουεϊ Έφτιαξε Μια Μηχανή Που Γεννά Πρώτους Αριθμούς

Ένας αλγόριθμος που γεννά πρώτους… με κλάσματα!

Φανταστείτε έναν υπολογιστή, όχι φτιαγμένο από κυκλώματα ή δυαδικούς αριθμούς, αλλά από μια λίστα με ρητούς αριθμούς — δεκατέσσερα κλάσματα. Και όμως, αυτός ο «υπολογιστής» μπορεί να παράγει, με μαθηματική αυστηρότητα, μια ακολουθία πρώτων αριθμών!

Αυτό είναι το Fractran, μια υπολογιστική γλώσσα φτιαγμένη από τον Τζον Χόρτον Κόνγουεϊ, και πιο συγκεκριμένα, η μηχανή παραγωγής πρώτων αριθμών του.

---

🔧 Πώς λειτουργεί η μηχανή;

Η διαδικασία έχει τρία απλά βήματα:

1. Ξεκινάς με έναν ακέραιο αριθμό — ξεκίνα από το 2.

2. Πολλαπλασιάζεις τον αριθμό αυτό με τα δεκατέσσερα συγκεκριμένα κλάσματα, με τη σειρά, μέχρι να βρεις ένα που δίνει ακέραιο αποτέλεσμα.

3. Το αποτέλεσμα αυτό γίνεται ο νέος αριθμός. Επαναλαμβάνεις.

🧪 Παράδειγμα εκκίνησης:

Αρχικός αριθμός: 2

Τα δεκατέσσερα κλάσματα είναι:

$\frac{17}{91},\ \frac{78}{85},\ \frac{19}{51},\ \frac{23}{38},\ \frac{29}{33},\ \frac{77}{29},\ \frac{95}{23},\ \frac{77}{19},\ \frac{1}{17},\ \frac{11}{13},\ \frac{13}{11},\ \frac{15}{14},\ \frac{15}{2},\ \frac{55}{1}$​

Στο πρώτο βήμα:
$2 \times \frac{17}{91} = \frac{34}{91}$ → όχι ακέραιος
$2 \times \frac{78}{85} = \frac{156}{85}$ → όχι ακέραιος
...
$2 \times \frac{15}{2} = 15$ → ✔ ακέραιος!

Άρα ο επόμενος αριθμός είναι το 15. Συνεχίζεις ξανά με τα ίδια κλάσματα.

---

📈 Τι παράγει αυτή η παράξενη διαδικασία;

Κάθε φορά που το αποτέλεσμα είναι μια δύναμη του 2 (όπως $2, 4, 8, 16, \ldots$), αυτό σηματοδοτεί την εμφάνιση ενός πρώτου αριθμού.

• Στο 19ο βήμα εμφανίζεται το 4 → που αντιστοιχεί στον πρώτο εκθέτη 2.

• Πενήντα βήματα αργότερα εμφανίζεται το 8 → εκθέτης 3.

• Περίπου 200 βήματα πιο κάτω εμφανίζεται το 32 → εκθέτης 5.

Το μοτίβο των εκθετών που εμφανίζονται είναι: 2, 3, 5, 7, 11, 13, 17, 19, ... — οι πρώτοι αριθμοί!

---

🤖 Μα είναι δυνατόν;

Ναι! Ο Κόνγουεϊ απέδειξε ότι αυτός ο απλός αλγόριθμος παράγει όλους τους πρώτους αριθμούς, σε μορφή δυνάμεων του 2. Το πιο εντυπωσιακό;

Όλα αυτά βασίζονται μόνο σε απλά πολλαπλασιαστικά βήματα με ρητούς αριθμούς.

Αυτή η διαδικασία είναι στην πραγματικότητα ένα παράδειγμα από μια αφηρημένη υπολογιστική γλώσσα, την Fractran (fraction + FORTRAN), που επινόησε ο ίδιος ο Κόνγουεϊ.

---

🧠 Γιατί είναι σημαντικό;

• Η γλώσσα Fractran έχει αποδειχτεί Turing-πλήρης! Δηλαδή, θεωρητικά μπορεί να υπολογίσει οτιδήποτε μπορεί να υπολογίσει ένας υπολογιστής.

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

---

✨ Τι είπε ο Ντόμινικ Ολιβάστρο;

«Αυτά τα δεκατέσσερα κλάσματα από μόνα τους έχουν την ικανότητα να παράγουν μια άπειρη γκάμα πρώτων αριθμών, ακόμη και εκείνων που κανείς δεν γνωρίζει ακόμη. Υπάρχει κάτι εξαιρετικά μαγικό σε αυτό.»