Ακολουθία Κολακόσκι

Στα μαθηματικά, η ακολουθία Κολακόσκι, η οποία μερικές φορές αναφέρεται και ως ακολουθία Όλντενμπουργκερ-Κολακόσκι, είναι μια άπειρη ακολουθία συμβόλων {1,2} που είναι η σειρά των διαδρόμων στην κωδικοποίηση του δικού της διαδρόμου. Πήρε το όνομά της από τον ψυχαγωγικό μαθηματικό Ουίλιαμ Κολακόσκι (1944-97), ο οποίος την περιέγραψε το 1965, αλλά είχε ήδη συζητηθεί από τον Ρούφους Όλντενμπουργκερ το 1939.

Ορισμός

Οι αρχικοί όροι της ακολουθίας Κολακόσκι είναι οι εξής:

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,... 

Κάθε σύμβολο εμφανίζεται σε μια "διαδρομή" (μια ακολουθία ίσων στοιχείων) είτε ενός είτε δύο διαδοχικών όρων και η καταγραφή των μηκών αυτών των διαδρομών δίνει ακριβώς την ίδια ακολουθία:

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...

1, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1, 2 ,...

Η περιγραφή της ακολουθίας Κολακόσκι είναι επομένως αναστρέψιμη. Αν Κ συμβολίζει την "ακολουθία Κολακόσκι", η περιγραφή #1 προϋποθέτει λογικά την περιγραφή #2 (και αντίστροφα):

1. Οι όροι του K παράγονται από τις διαδρομές (δηλαδή τα μήκη διαδρομής) του K
2. Οι διαδρομές του K παράγονται από τους όρους του K.

Κατά συνέπεια, μπορούμε να πούμε ότι κάθε όρος της ακολουθίας Κολακόσκι δημιουργεί μια σειρά ενός ή δύο μελλοντικών όρων. Το πρώτο 1 της ακολουθίας παράγει μια σειρά του "1", δηλαδή τον εαυτό του- το πρώτο 2 παράγει μια σειρά του "22", η οποία περιλαμβάνει τον εαυτό του- το δεύτερο 2 παράγει μια σειρά του "11"- και ούτω καθεξής. Κάθε αριθμός στην ακολουθία είναι το μήκος της επόμενης σειράς που θα παραχθεί, και το στοιχείο που θα παραχθεί εναλλάσσεται μεταξύ 1 και 2:

1,2 (μήκος της ακολουθίας l = 2; άθροισμα των όρων s = 3)
1,2,2 (l = 3, s = 5)
1,2,2,1,1 (l = 5, s = 7)
1,2,2,1,1,2,1 (l = 7, s = 10)
1,2,2,1,1,2,1,2,2,1 (l = 10, s = 15)
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 (l = 15, s = 23)

Όπως φαίνεται, το μήκος της ακολουθίας σε κάθε στάδιο είναι ίσο με το άθροισμα των όρων του προηγούμενου σταδίου. Αυτό το κινούμενο σχέδιο απεικονίζει τη διαδικασία:

Αυτές οι αυτοδημιουργούμενες ιδιότητες, οι οποίες παραμένουν αν η ακολουθία γραφτεί χωρίς το αρχικό 1, σημαίνουν ότι η ακολουθία Κολακόσκι μπορεί να περιγραφεί ως φράκταλ, ή μαθηματικό αντικείμενο που κωδικοποιεί τη δική του αναπαράσταση σε άλλες κλίμακες.Ο Μπερτράν Στάινσκι δημιούργησε έναν αναδρομικό τύπο για τον i-th όρο της ακολουθίας, αλλά η ακολουθία εικάζεται ότι είναι απεριοδική,  πράγμα που σημαίνει ότι οι όροι της δεν έχουν ένα γενικό επαναλαμβανόμενο μοτίβο (βλ. άρρητοι αριθμοί όπως π και ).

Έρευνα

Πυκνότητα
Φαίνεται εύλογο ότι η πυκνότητα των 1s στην {1,2}-ακολουθία του Κολακόσκι είναι 1/2, αλλά αυτή η εικασία παραμένει αναπόδεικτη . Ο Βακλάβ Τσβάταλ απέδειξε ότι η ανώτερη πυκνότητα των 1s είναι μικρότερη από 0,50084. Ο Νίλσον χρησιμοποίησε την ίδια μέθοδο με πολύ μεγαλύτερη υπολογιστική ισχύ για να επιτύχει το όριο 0,500080.

Αν και οι υπολογισμοί των πρώτων 3×108 τιμών της ακολουθίας φάνηκε να δείχνουν ότι η πυκνότητά της συγκλίνει σε μια τιμή ελαφρώς διαφορετική από το 1/2, μεταγενέστεροι υπολογισμοί που επέκτειναν την ακολουθία στις πρώτες 1013 τιμές της δείχνουν ότι η απόκλιση από την πυκνότητα του 1/2 γίνεται όλο και μικρότερη, όπως θα περίμενε κανείς αν η οριακή πυκνότητα είναι πράγματι 1/2.

Σύνδεση με συστήματα επισήμανσης
Η ακολουθία Κολακόσκι μπορεί επίσης να περιγραφεί ως το αποτέλεσμα ενός απλού κυκλικού συστήματος ετικετών. Ωστόσο, καθώς αυτό το σύστημα είναι ένα σύστημα 2 ετικετών και όχι ένα σύστημα 1 ετικέτας (δηλαδή αντικαθιστά ζεύγη συμβόλων με άλλες ακολουθίες συμβόλων, αντί να λειτουργεί σε ένα μόνο σύμβολο κάθε φορά), βρίσκεται στην περιοχή των παραμέτρων για τις οποίες τα συστήματα ετικετών είναι πλήρη κατά Τούρινγκ, γεγονός που καθιστά δύσκολη τη χρήση αυτής της αναπαράστασης για τη συλλογιστική της ακολουθίας.

Αλγόριθμοι
Η ακολουθία Κολακόσκι μπορεί να παραχθεί από έναν αλγόριθμο που, στην i-th επανάληψη, διαβάζει την τιμή xi  που έχει ήδη εκδοθεί ως την i-th  τιμή της ακολουθίας (ή, αν δεν έχει εκδοθεί ακόμη τέτοια τιμή, θέτει xi = i). Στη συνέχεια, αν το i είναι περιττό, εξάγει xi αντίγραφα του αριθμού 1, ενώ αν το i είναι άρτιο, εξάγει  xi αντίγραφα του αριθμού 2. Έτσι, τα πρώτα βήματα του αλγορίθμου είναι τα εξής:
Η πρώτη τιμή δεν έχει ακόμη εκδοθεί, οπότε ορίστε  x1 = 1 και δώστε 1 αντίγραφο του αριθμού 1.
Η δεύτερη τιμή δεν έχει ακόμη εξαχθεί, οπότε θέστε x2 = 2 και εξάγετε 2 αντίγραφα του αριθμού 2.
Η τρίτη τιμή x3 εξήχθη ως 2 στο δεύτερο βήμα, οπότε εξάγετε 2 αντίγραφα του αριθμού 1.
Η τέταρτη τιμή x4 εξήχθη ως 1 στο τρίτο βήμα, οπότε εξάγετε 1 αντίγραφο του αριθμού 2. κ.λπ.

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

Δημοσιεύσεις

Δείτε επίσης 
Αυτοομοιότητα
Σύνολο Μάντελμπροτ 
Σύνολο Julia
Οικοδομήσιμο Σύμπαν

Παραπομπές

 
 
Φράκταλ
Ακολουθίες ακεραίων