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

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

Απεικόνιση του 3ου έως 50ου όρου της ακολουθίας Κολακόσκι ως σπείρα. Οι όροι ξεκινούν από την κουκκίδα στη μέση της σπείρας. Στην επόμενη περιστροφή, κάθε τόξο επαναλαμβάνεται αν ο όρος είναι 1, ή χωρίζεται σε δύο ίσα μισά αν είναι 2. Οι δύο πρώτοι όροι δεν μπορούν να απεικονιστούν καθώς είναι αυτοαναφορικοί. Στο the SVG image, περάστε με το ποντίκι πάνω από ένα τόξο ή μια ετικέτα για να το επισημάνετε και να εμφανίσετε τα στατιστικά του στοιχεία.

Ορισμός

Η ακολουθία Κολακόσκι περιγράφει το δικό της μήκος διαδρομής

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

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,... (ακολουθία A000002 στην OEIS)

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

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)

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

Ένα κινουμένο gif που απεικονίζει πώς οι μεταγενέστεροι όροι της ακολουθίας Κολακόσκι παράγονται από τους προηγούμενους όρους.

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

Έρευνα

Πυκνότητα

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

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

Σύνδεση με συστήματα επισήμανσης

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

Αλγόριθμοι

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

1. Η πρώτη τιμή δεν έχει ακόμη εκδοθεί, οπότε ορίστε x₁ = 1 και δώστε 1 αντίγραφο του αριθμού 1.
2. Η δεύτερη τιμή δεν έχει ακόμη εξαχθεί, οπότε θέστε x₂ = 2 και εξάγετε 2 αντίγραφα του αριθμού 2.
3. Η τρίτη τιμή x₃ εξήχθη ως 2 στο δεύτερο βήμα, οπότε εξάγετε 2 αντίγραφα του αριθμού 1.
4. Η τέταρτη τιμή x₄ εξήχθη ως 1 στο τρίτο βήμα, οπότε εξάγετε 1 αντίγραφο του αριθμού 2. κ.λπ.

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

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

• Allouche, Jean-Paul· Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. σελ. 337. ISBN 978-0-521-82332-6. Zbl 1086.11015. 
• Dekking, F. M. (1997). «What Is the Long Range Order in the Kolakoski Sequence?». Στο: Moody, R. V., επιμ. Dordrecht, Netherlands: Kluwer, pp. 115–125. 
• Fedou, J. M.; Fici, G. (2010). «Some remarks on differentiable sequences and recursivity». Journal of Integer Sequences 13 (3): Article 10.3.2. http://hal.archives-ouvertes.fr/docs/00/46/35/72/PDF/Some_remarks_on_differentiable_sequences_and_recursivity.pdf. 
• Keane, M. S. (1991). «Ergodic Theory and Subshifts of Finite Type». Στο: Bedford, T.; Keane, M., επιμ. Oxford, England: Oxford University Press, pp. 35–70. 
• Lagarias, J. C. (1992). «Number Theory and Dynamical Systems». Στο: Burr, S. A., επιμ. Providence, RI: American Mathematical Society, pp. 35–72. ISBN 9780821855010. https://books.google.com/books?id=j-pLi01XbFUC&pg=PA35. 
• Păun, Gheorghe; Salomaa, Arto (1996). «Self-Reading Sequences». American Mathematical Monthly 103 (2): 166–168. doi:10.2307/2975113. . 
• Shallit, Jeffrey (1999). «Number theory and formal languages». Στο: Hejhal, Dennis A.· Friedman, Joel· Gutzwiller, Martin C.· Odlyzko, Andrew M. Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15--26, 1996. The IMA volumes in mathematics and its applications. 109. Springer-Verlag. σελίδες 547–570. ISBN 0-387-98824-6. Zbl 0919.00047. 

Δείτε επίσης

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