Ισχύουσα διάσταση

Στα μαθηματικά, η ισχύουσα διάσταση^[1] είναι μια τροποποίηση της διάστασης Χάουσντορφ^[2] και άλλων μορφοκλασματικών διαστάσεων, η οποία την τοποθετεί στο πλαίσιο της θεωρίας υπολογισιμότητας. Υπάρχουν διάφορες παραλλαγές (διαφορετικές έννοιες της ισχύουσας διάστασης), η πιο συνηθισμένη από τις οποίες είναι η ισχύουσα διάσταση του Χάουσντορφ. Στα μαθηματικά, η διάσταση είναι ένας ιδιαίτερος τρόπος περιγραφής του μεγέθους ενός αντικειμένου (σε αντίθεση με τη μέτρηση και άλλες έννοιες διαφορετικές από το μέγεθος). Η διάσταση Χάουστορφ γενικεύει τις γνωστές ακέραιες διαστάσεις που αποδίδονται σε σημεία, γραμμές, επίπεδα κ.λπ., καθιστώντας δυνατή τη διάκριση αντικειμένων ενδιάμεσου μεγέθους μεταξύ αυτών των αντικειμένων ακέραιων διαστάσεων.^[3]

Παραδείγματος χάριν, τα μορφοκλασματικά υποσύνολα του επιπέδου μπορούν να έχουν μια ενδιάμεση διάσταση μεταξύ 1 και 2, επειδή είναι "μεγαλύτερα" από τις γραμμές ή τις καμπύλες, και όμως "μικρότερα" από τους κύκλους ή τα συμπαγή ορθογώνια. Η ισχύουσα διάσταση τροποποιεί τη διάσταση Χάουσντορφ απαιτώντας ότι τα αντικείμενα με μικρή ισχύουσα διάσταση δεν είναι μόνο μικρά αλλά και εντοπίσιμα (ή μερικώς εντοπίσιμα) με μια υπολογίσιμη έννοια. Έτσι, αντικείμενα με μεγάλη διάσταση Χάουσντορφ έχουν επίσης μεγάλη ισχύουσα διάσταση, και αντικείμενα με μικρή ισχύουσα διάσταση έχουν μικρή διάσταση Χάουσντορφ, αλλά ένα αντικείμενο μπορεί να έχει μικρή διάσταση Χάουσντορφ αλλά μεγάλη ισχύουσα διάσταση. Ένα παράδειγμα είναι ένα αλγοριθμικά τυχαίο σημείο σε μια γραμμή, το οποίο έχει διάσταση Χάουσντορφ 0 (επειδή είναι σημείο) αλλά ισχύουσα διάσταση 1 (επειδή, κατά προσέγγιση, δεν μπορεί να εντοπιστεί καλύτερα από ένα μικρό διάστημα, το οποίο έχει διάσταση Χάουσντορφ 1).

Αυστηροί ορισμοί

Αυτό το λήμμα ορίζει την ισχύουσα διάσταση για υποσύνολα του χώρου Κάντορ^[4] 2^ω; πολύ παρόμοιοι ορισμοί υπάρχουν για υποσύνολα του ευκλείδειου χώρου Rⁿ. Θα κινούμαστε ελεύθερα από ένα σύνολο X φυσικών αριθμών στην άπειρη ακολουθία $\chi _{X}$ που δίνεται από τη χαρακτηριστική συνάρτηση του X, και στον πραγματικό αριθμό με το δυαδικό ανάπτυγμα 0.X.

Προσέγγιση (Martingale) και gale

Μια προσέγγιση (Martingale)^[5] στον χώρο Κάντορ 2^ω είναι μια συνάρτηση d: 2^ω → R^≥ 0 από τον χώρο Κάντορ στους μη αρνητικούς πραγματικούς που ικανοποιεί τη συνθήκη ισοτιμίας :

d(\sigma )={\frac {1}{2}}(d(\sigma 0)+d(\sigma 1))

Μια προσέγγιση (Martingale)^[5] θεωρείται ως μια στρατηγική στοιχηματισμού και η συνάρτηση $d(\sigma )$ δίνει το κεφάλαιο του καλύτερου αφού δει μια ακολουθία σ από 0s και 1s. Η συνθήκη της ισοτιμίας λέει τότε ότι το κεφάλαιο μετά από μια ακολουθία σ είναι ο μέσος όρος του κεφαλαίου αφού δει σ0 και σ1. Με άλλα λόγια, η προσέγγιση (Martingale) δίνει ένα στοιχηματικό σχήμα για έναν πράκτορα στοιχημάτων με αποδόσεις 2:1 που προσφέρονται σε μία από τις δύο "εξίσου πιθανές" επιλογές, εξ ου και η ονομασία "ισοτιμία".

(Να σημειωθεί ότι αυτό διαφέρει ελαφρώς από την έννοια της martingale της θεωρίας πιθανοτήτων. Αυτός ο ορισμός της martingale^[6] έχει μια παρόμοια συνθήκη ισοτιμίας, η οποία επίσης δηλώνει ότι η αναμενόμενη τιμή μετά από κάποια παρατήρηση είναι η ίδια με την τιμή πριν από την παρατήρηση, δεδομένης της προηγούμενης ιστορίας των παρατηρήσεων. Η διαφορά είναι ότι στη θεωρία πιθανοτήτων, το προηγούμενο ιστορικό των παρατηρήσεων αναφέρεται απλώς στο ιστορικό του κεφαλαίου, ενώ εδώ το ιστορικό αναφέρεται στην ακριβή ακολουθία των 0 και 1 της συμβολοσειράς).

Μια supermartingale^[7] στο χώρο Κάντορ είναι μια συνάρτηση d όπως παραπάνω που ικανοποιεί μια τροποποιημένη συνθήκη ισοτιμίας:

d(\sigma )\geq {\frac {1}{2}}(d(\sigma 0)+d(\sigma 1))

Η supermartingale (υπερ-προσέγγιση) είναι μια στρατηγική στοιχηματισμού όπου το αναμενόμενο κεφάλαιο μετά από ένα στοίχημα δεν είναι μεγαλύτερο από το κεφάλαιο πριν από ένα στοίχημα, σε αντίθεση με τη προσέγγιση όπου τα δύο είναι πάντα ίσα. Αυτό επιτρέπει μεγαλύτερη ευελιξία, και είναι πολύ παρόμοιο στην μη αποτελεσματική περίπτωση, αφού κάθε φορά που δίνεται μια supermartingale d, υπάρχει μια τροποποιημένη συνάρτηση d που κερδίζει τουλάχιστον τόσα χρήματα όσο η d και η οποία είναι στην πραγματικότητα μια προσέγγιση . Ωστόσο, είναι χρήσιμο να επιτρέψουμε την πρόσθετη ευελιξία μόλις αρχίσουμε να μιλάμε για την παροχή αλγορίθμων για τον προσδιορισμό της στρατηγικής στοιχηματισμού, καθώς ορισμένοι αλγόριθμοι προσφέρονται πιο φυσικά για την παραγωγή supermartingale παρά martingale.

Μια s-gale είναι μια συνάρτηση d όπως παραπάνω της μορφής

d(\sigma )={\frac {e(\sigma )}{2^{(1-s)|\sigma |}}}

για e κάποιο martingale.

Μια s-supergale είναι μια συνάρτηση d όπως παραπάνω της μορφής

d(\sigma )={\frac {e(\sigma )}{2^{(1-s)|\sigma |}}}

για e κάποια supermartingale.

Μια s-(super)gale είναι μια στρατηγική στοιχηματισμού όπου σε κάθε βήμα χάνεται κάποιο ποσό κεφαλαίου από τον πληθωρισμό. Σημειώστε ότι οι s-gales και οι s-upergales είναι παραδείγματα των supermartingales, και οι 1-gale και 1-supergale είναι ακριβώς οι martingales και οι supermartingales.

Από κοινού, τα αντικείμενα αυτά είναι γνωστά ως "gale ^[7]".

Μια gale^[7] d πετυχαίνει σε ένα υποσύνολο X των φυσικών αριθμών αν $\limsup _{n}d(X|n)=\infty$ όταν $X|n$ όπου $X|n$ δηλώνει n-ψήφια συμβολοσειρά που αποτελείται από τα πρώτα n ψηφία του X.

Μια gale^[7] d έχει υψηλή επιτυχία στο X αν $\liminf _{n}d(X|n)=\infty$ .

Όλες αυτές οι έννοιες των διαφόρων gales^[7] δεν έχουν αποτελεσματικό περιεχόμενο, αλλά πρέπει αναγκαστικά να περιοριστεί κανείς σε μια μικρή κατηγορία gales, αφού μπορεί να βρεθεί κάποια gales που να πετυχαίνει σε κάθε δεδομένο σύνολο. Εξάλλου, αν κάποιος γνωρίζει εκ των προτέρων μια ακολουθία από ρίψεις νομισμάτων, είναι εύκολο να βγάλει χρήματα απλά στοιχηματίζοντας στα γνωστά αποτελέσματα κάθε ρίψης. Ένας συνηθισμένος τρόπος για να γίνει αυτό είναι να απαιτήσουμε τα gales^[7] να είναι είτε υπολογίσιμα είτε σχεδόν υπολογίσιμα:

Μια gale d ονομάζεται εποικοδομητική, c.e., ή κάτω ημι-υπολογίσιμη αν οι αριθμοί $d(\sigma )$ είναι ομοιόμορφα αριστερά-c.e. πραγματικοί (δηλαδή μπορούν ομοιόμορφα να γραφούν ως το όριο μιας αυξανόμενης υπολογίσιμης ακολουθίας λογικών).

Η ισχύουσα διάσταση Χάουσντορφ ενός συνόλου φυσικών αριθμών Χ είναι $\inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ on\ } X\}$ ^[8]

Η ισχύουσα διάσταση συσκευασίας του X είναι $\inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ strongly\ on\ } X\}$ .^[9]

Ορισμός της πολυπλοκότητας Κολόγκοροφ

Η πολυπλοκότητα του Κολμογκόροφ μπορεί να θεωρηθεί ως ένα κατώτερο όριο για την αλγοριθμική συμπιεστότητα μιας πεπερασμένης ακολουθίας (δυαδικών χαρακτήρων ή ψηφίων). Αποδίδει σε κάθε μία από αυτές τις ακολουθίες "w" έναν φυσικό αριθμό "K(w)" ο οποίος, διαισθητικά, μετρά το ελάχιστο μήκος ενός προγράμματος υπολογιστή (γραμμένου σε μια σταθερή γλώσσα προγραμματισμού) που δεν δέχεται καμία είσοδο και παράγει "w" όταν εκτελείται.

Η ισχύουσα διάσταση Χάουσντορφ ενός συνόλου φυσικών αριθμών Χ είναι $\liminf _{n}{\frac {K(X|n)}{n}}$ .^[10]^[11]^[12]^[13]

Η ισχύουσα διάσταση συσκευασίας ενός συνόλου X είναι $\limsup _{n}{\frac {K(X|n)}{n}}$ .^[9]^[10]^[11]

Από αυτό μπορεί κανείς να δει ότι τόσο η ισχύουσα διάσταση Χάουσντορφ όσο και η ισχύουσα διάσταση συσκευασίας ενός συνόλου είναι μεταξύ 0 και 1, με την πραγματική διάσταση συσκευασίας να είναι πάντα τουλάχιστον τόσο μεγάλη όσο η ισχύουσα διάσταση Χάουσντορφ. Κάθε τυχαία ακολουθία θα έχει ισχύουσα διάσταση Χάουσντορφ και διάσταση συσκευασίας ίση με 1, αν και υπάρχουν και μη τυχαίες ακολουθίες με ισχύουσα διάσταση Χάουσντορφ και διάσταση συσκευασίας 1.

Σύγκριση με την κλασική διάσταση

Αν το Z είναι ένα υποσύνολο του 2'^ω, η διάστασή Χάουσντορφ είναι $\inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ on\ all\ elements\ of\ } Z\}$ .^[8]

Η διάσταση συσκευασίας του Z είναι $\inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ strongly\ on\ all\ elements\ of\ } Z\}$ .^[9]

Έτσι, οι πραγματικές διαστάσεις Χάουσντορφ και συσκευασίας ενός συνόλου $X$ είναι απλώς οι κλασικές διαστάσεις Χάουσντορφ και συσκευασίας του $\{X\}$ (αντίστοιχα) όταν περιορίζουμε την προσοχή μας σε γ.ε. "gale^[7]".

Να οριστούν τα ακόλουθα στοιχεία:

H_{\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } \beta \}

H_{\leq \beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } \leq \beta \}

H_{<\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } <\beta \}

P_{\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } \beta \}

P_{\leq \beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } \leq \beta \}

P_{<\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } <\beta \}

Συνέπεια των προαναφερθέντων είναι ότι όλα αυτά έχουν διάσταση Χάουσντορφ $\beta$ .^[14]

$H_{\beta },H_{\leq \beta }$ και $H_{<\beta }$ όλα έχουν διάσταση συσκευασίας 1.

$P_{\beta },P_{\leq \beta }$ και $P_{<\beta }$ όλα έχουν διάσταση συσκευασίας $\beta$ .

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

J. H. Lutz (2005). «Effective fractal dimensions». Mathematical Logic Quarterly 51 (1): 62–72. doi:10.1002/malq.200310127. [1]
J. Reimann (2004). Computability and fractal dimension, PhD thesis. Ruprecht-Karls Universität Heidelberg. [2]
L. Staiger (2007). «The Kolmogorov complexity of infinite words». Theoretical Computer Science 383 (2–3): 187–199. doi:10.1016/j.tcs.2007.04.013. [3]

Δείτε επίσης

Παραπομπές

↑ «Παράλληλη Επιτάχυνση αλγορίθμων Dictionary Learning -1.1 Dictionary Learning- σελίδα 14» (PDF).
↑ Shen, A.· Uspensky, V. A. (18 Μαΐου 2022). Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society. ISBN 978-1-4704-7064-7.
↑ Cámara, Elvira Mayordomo (2004). Löwe, Benedikt, επιμ (στα αγγλικά). Effective Hausdorff dimension. 23. Dordrecht: Springer Netherlands, σελ. 171–186. doi:10.1007/978-1-4020-2776-5_10. ISBN 978-1-4020-2775-8. http://link.springer.com/10.1007/978-1-4020-2776-5_10.
↑ «Cantor space in nLab». ncatlab.org. Ανακτήθηκε στις 2 Ιανουαρίου 2024.
↑ ^5,0 ^5,1 «Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου» (PDF).
↑ John M. Hitchcock; Jack H. Lutz (2006). «Why computational complexity requires stricter martingales». Theory of Computing Systems.
↑ ^7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 ^7,6 «gale». planetmath.org. Ανακτήθηκε στις 2 Ιανουαρίου 2024.
↑ ^8,0 ^8,1 Jack H. Lutz (2003). «Dimension in complexity classes». SIAM Journal on Computing 32 (5): 1236–1259. doi:10.1137/s0097539701417723.
↑ ^9,0 ^9,1 ^9,2 Krishna B. Athreya; John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (2007). «Effective strong dimension in algorithmic information and computational complexity». SIAM Journal on Computing 37 (3): 671–705. doi:10.1137/s0097539703446912.
↑ ^10,0 ^10,1 Jin-yi Cai; Juris Hartmanis (1994). «On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.». Journal of Computer and System Sciences 49 (3): 605–619. doi:10.1016/S0022-0000(05)80073-X.
↑ ^11,0 ^11,1 Ludwig Staiger (1993). «Kolmogorov complexity and Hausdorff dimension.». Information and Computation 103 (2): 159–194. doi:10.1006/inco.1993.1017.
↑ Elvira Mayordomo (2002). «A Kolmogorov complexity characterization of constructive Hausdorff dimension.». Information Processing Letters 84: 1–3. doi:10.1016/S0020-0190(02)00343-5.
↑ Ludwig Staiger (2005). «Constructive dimension equals Kolmogorov complexity.». Information Processing Letters 93 (3): 149–153. doi:10.1016/j.ipl.2004.09.023.
↑ Boris Ryabko (1994). «Coding of combinatorial sources and Hausdorff dimension.». Soviet Mathematics - Doklady.

[1] «Παράλληλη Επιτάχυνση αλγορίθμων Dictionary Learning -1.1 Dictionary Learning- σελίδα 14» (PDF).

[2] Shen, A.· Uspensky, V. A. (18 Μαΐου 2022). Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society. ISBN 978-1-4704-7064-7.

[3] Cámara, Elvira Mayordomo (2004). Löwe, Benedikt, επιμ (στα αγγλικά). Effective Hausdorff dimension. 23. Dordrecht: Springer Netherlands, σελ. 171–186. doi:10.1007/978-1-4020-2776-5_10. ISBN 978-1-4020-2775-8. http://link.springer.com/10.1007/978-1-4020-2776-5_10.

[4] «Cantor space in nLab». ncatlab.org. Ανακτήθηκε στις 2 Ιανουαρίου 2024.

[:1-5] 5,0 ^5,1 «Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου» (PDF).

[wccrsm-6] John M. Hitchcock; Jack H. Lutz (2006). «Why computational complexity requires stricter martingales». Theory of Computing Systems.

[:0-7] 7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 ^7,6 «gale». planetmath.org. Ανακτήθηκε στις 2 Ιανουαρίου 2024.

[dicc-8] 8,0 ^8,1 Jack H. Lutz (2003). «Dimension in complexity classes». SIAM Journal on Computing 32 (5): 1236–1259. doi:10.1137/s0097539701417723.

[efsdiaiacc-9] 9,0 ^9,1 ^9,2 Krishna B. Athreya; John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (2007). «Effective strong dimension in algorithmic information and computational complexity». SIAM Journal on Computing 37 (3): 671–705. doi:10.1137/s0097539703446912.

[caha-10] 10,0 ^10,1 Jin-yi Cai; Juris Hartmanis (1994). «On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.». Journal of Computer and System Sciences 49 (3): 605–619. doi:10.1016/S0022-0000(05)80073-X.

[koha-11] 11,0 ^11,1 Ludwig Staiger (1993). «Kolmogorov complexity and Hausdorff dimension.». Information and Computation 103 (2): 159–194. doi:10.1006/inco.1993.1017.

[akccochd-12] Elvira Mayordomo (2002). «A Kolmogorov complexity characterization of constructive Hausdorff dimension.». Information Processing Letters 84: 1–3. doi:10.1016/S0020-0190(02)00343-5.

[cdko-13] Ludwig Staiger (2005). «Constructive dimension equals Kolmogorov complexity.». Information Processing Letters 93 (3): 149–153. doi:10.1016/j.ipl.2004.09.023.

[rya-14] Boris Ryabko (1994). «Coding of combinatorial sources and Hausdorff dimension.». Soviet Mathematics - Doklady.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]