Computability and fractal dimension [Elektronische Ressource] / vorgelegt von Jan Reimann

INAUGURALDISSERTATIONzurErlangungderDoktorwurde¨der¨Naturwissenschaftlich MathematischenGesamtfakult atderRuprecht Karls Universit at¨HeidelbergvorgelegtvonDiplom MathematikerJanReimannausKoln¨Tagdermundlichen¨ Prufung:¨ 22. Dezember2004ThemaComputabilityandFractalDimensionGutachter: Prof. Dr. KlausAmbos SpiesPDDr. WolfgangMerkleAbstraktDie vorliegende Arbeit verbindet Berechenbarkeitstheorie mit einigen Begriffen fraktalerDimension. EinalgorithmischerZugangzuHausdorff Maßenerm oglicht¨ es,dieHausdorff Dimension von einzelnen Punkten anstelle von Teilmengen eines metrischen Raumes zudefinieren. Diese Idee wurde erstmals von Lutz (2000b) verwirklicht. Wir arbeiten hier-ω ¨ ¨bei im Cantorraum 2 , bestehend aus allen unendlichen Binarfolgen. Wir geben zunachst¨einen Uberblick uber¨ die wichtigsten Definitionen und Eigenschaften der verschiedenenBegriffe fraktaler Dimension im Cantorraum. Danach entwickeln wir die Theorie der ef fektiven Dimension systematisch, auf der Grundlage des Zugangs zur algorithmischen In formationstheorie, welcher von Kolmogorov und seinen Schulern¨ entwickelt wurde. Aufdiese Weise konnen¨ wir ein zentrales Resultat der effektiven Hausdorff Dimension aufneue und einfache Weise herleiten: Die effektive Hausdorff Dimension einer Folge ent sprichtihrerunterenasymptotischenalgorithmischenEntropie,definiertuber¨ Kolmogorov Komplexitat.
Publié le : samedi 1 janvier 2005
Lecture(s) : 38
Source : ARCHIV.UB.UNI-HEIDELBERG.DE/VOLLTEXTSERVER/VOLLTEXTE/2005/5543/PDF/DISSERTATION_REIMANN_2004.PDF
Nombre de pages : 153
Voir plus Voir moins

INAUGURALDISSERTATION
zur
ErlangungderDoktorwurde¨
der
¨Naturwissenschaftlich MathematischenGesamtfakult at
der
Ruprecht Karls Universit at¨
Heidelberg
vorgelegtvon
Diplom MathematikerJanReimann
ausKoln¨
Tagdermundlichen¨ Prufung:¨ 22. Dezember2004Thema
Computability
and
FractalDimension
Gutachter: Prof. Dr. KlausAmbos Spies
PDDr. WolfgangMerkleAbstrakt
Die vorliegende Arbeit verbindet Berechenbarkeitstheorie mit einigen Begriffen fraktaler
Dimension. EinalgorithmischerZugangzuHausdorff Maßenerm oglicht¨ es,dieHausdorff
Dimension von einzelnen Punkten anstelle von Teilmengen eines metrischen Raumes zu
definieren. Diese Idee wurde erstmals von Lutz (2000b) verwirklicht. Wir arbeiten hier-
ω ¨ ¨bei im Cantorraum 2 , bestehend aus allen unendlichen Binarfolgen. Wir geben zunachst
¨einen Uberblick uber¨ die wichtigsten Definitionen und Eigenschaften der verschiedenen
Begriffe fraktaler Dimension im Cantorraum. Danach entwickeln wir die Theorie der ef
fektiven Dimension systematisch, auf der Grundlage des Zugangs zur algorithmischen In
formationstheorie, welcher von Kolmogorov und seinen Schulern¨ entwickelt wurde. Auf
diese Weise konnen¨ wir ein zentrales Resultat der effektiven Hausdorff Dimension auf
neue und einfache Weise herleiten: Die effektive Hausdorff Dimension einer Folge ent
sprichtihrerunterenasymptotischenalgorithmischenEntropie,definiertuber¨ Kolmogorov
Komplexitat.¨ AußerdembeweisenwireinallgemeinesResultathinsichtlichdesVerhaltens
voneffektiverHausdorff Dimensionunter r expansivenAbbildungen,welcheeineVerall
gemeinerung von Holder¨ Transformationen im Cantorraum darstellen. Wir untersuchen
den Zusammenhang zwischen anderen effektiven Dimensionsbegriffen und algorithmi
scher Entropie. Daruberhinaus¨ konnen¨ wir zeigen, daß die Menge aller Folgen, welche
effektive Hausdorff Dimension s besitzen, Hausdorff Dimension s sowie unendliches s-
dimensionalesHausdorff Maßhat(f ur¨ 0< s < 1).
EsfolgteineUntersuchungderHausdorff Dimension(klassischwieeffektiv)vonOb
jekten, welche in der Berechenbarkeitstheorie auftreten. Wir beweisen, daß der obere
Kegel einer Folge bezuglich¨ jeder der ublichen¨ Reduzierbarkeiten Hausdorff Dimension
1 besitzt und geben auf diese Weise ein Beispiel fur¨ eine Lebesgue Nullmenge maximaler
Dimension. Ferner benutzen wir die Resultate bezuglich¨ effektiverr expansiver Transfor-
mationen um zu zeigen, daß die effektive Dimension eines Grades der des zugehorigen¨
unterenKegelsentspricht. Fur¨ Many one ReduzierbarkeitbeweisenwirdieExistenzeines Kegels nicht ganzzahliger effektiver Hausdorff Dimension. Schließlich folgt der
ωBeweis,daßeffektiv abgeschlosseneMengen A⊆ 2 positiverHausdorff Dimensioneine
ωberechenbare,surjektiveAbbildungA→ 2 erlauben.
Danach wenden wir uns einem genaueren Studium der komplexen Wechselbeziehung
¨zwischen algorithmischer Entropie, Zufalligkeit, effektiver Hausdorff Dimension und Re
duzierbarkeitzu. ZudiesemZweckfuhren¨ wireineverallgemeinerteVersiondereffektiven
Hausdorff Dimensionein, uber¨ denBegriffdesstarkeneffektivenHausdorff Maßes0. Wir
konnen¨ zeigen, daß die Tatsache, daß eine Folge nicht starkes effektives Hausdorff Maß 0
hat,nichtnotwendigdieMoglichk¨ eitimpliziert,ausdieserFolgeeineMartin L of zuf¨ allige¨
Folge zu berechnen, eine Folge hochstm¨ oglicher¨ algorithmischer Entropie. Außerdem
zeigen wir, daß eine Verallgemeinerung des effektiven Zufalligk¨ eitsbegriffes auf nicht
berechenbareMaßeeinensehrumfassendenZufalligk¨ eitsbegriffzurFolgehat: Jedenicht Folgeistzufallig¨ bezuglich¨ einesMaßes.
Es folgt die Einfuhrung¨ von Schnorr Dimension, einem algorithmisch restriktiveren
Dimensionsbegriff als der effektiven Dimension. Wir leiten eine Maschinencharakter-
isierung der Schnorr Dimension her und zeigen, daß f ur¨ rekursiv aufz ahlbare¨ Mengen
Schnorr Hausdorff Dimension und Schnorr Packing Dimension nicht notwendig uberein ¨stimmenmussen,¨ imGegensatzzureffektivenDimension.
Desweiteren untersuchen wir subrekursive Dimensionsbegriffe. Unter der Verwen
¨ ¨ ¨dungvonressourcenbeschranktenMartingalenkonnenwirdieHoldertransformationstech
niken auf denankten¨ Fall ubertragen¨ und konnen¨ damit zeigen, daß das
Small Span TheoremimFallderHausdorff DimensioninExponentialzeitEnichtgilt.
Schließlich studieren wir die effektive Hausdorff Dimension von Folgen, gegen die
keine berechenbare, nichtmonotone Wettstrategie gewinnt. Berechenbare, nichtmonotone
WettspielesindeineVerallgemeinerungvonberechenbarenMartingalen,undesisteinof
fenesProblem,obderdaruber¨ definierteZufallsbegriffmitMartin L of Zuf¨ alligk¨ eitzusam
menfallt.¨ Wirzeigen,daßdieFolgen,welchezufallig¨ sindbzgl. berechenbarer,nichtmono
toner Wettspiele, effektive Hausdorff Dimension 1 haben m ussen,¨ was impliziert, daß,
unter dem Gesichtspunkt algorithmischer Entropie, solche Folgen recht nahe an Martin
Lof Zuf¨ alligk¨ eitsind.Abstract
Thisthesiscombinescomputabilitytheoryandvariousnotionsoffractaldimension,mainly
Hausdorff dimension. An algorithmic approach to Hausdorff measures makes it possible
to define the Hausdorff dimension of individual points instead of sets in a metric space.
ωThis idea was first realized by Lutz (2000b). Working in the Cantor space 2 of all in
finite binary sequences, we study the theory of Hausdorff and other dimensions for indi
vidual sequences. After giving an overview over the classical theory of fractal dimension
in Cantor space, we develop the theory of effective Hausdorff dimension and its variants
systematically. Our presentation is inspired by the approach to algorithmic information
theory developed by Kolmogorov and his students. We are able to give a new and much
easier proof of a central result of the effective theory: Effective Hausdorff dimension co
incides with the lower asymptotic algorithmic entropy, defined in terms of Kolmogorov
complexity. Besides, we prove a general theorem on the behavior of effective dimension
under r expansive mappings, which can be seen as a generalization of H older¨ mappings
ωin 2 . Furthermore, we study the connections between other notions of effective fractal
dimensionandalgorithmicentropy. Besides,weareabletoshowthatthesetofsequences
of effective Hausdorff dimension s has Hausdorff dimension s and infinite s dimensional
Hausdorffmeasure(forevery0< s < 1).
Next, we study the Hausdorff dimension (effective and classical) of objects arising
in computability theory. We prove that the upper cone of any sequence under a standard
reducibilityhasHausdorffdimension1,therebyexposingaLebesguenullsetthathasmax
imal Hausdorff dimension. Furthermore, using the behavior of effective dimension under
r expansive transformations, we are able to show that the effective Hausdorff dimension
of the lower cone and the degree of a sequence coincide. For many one reducibility, we
prove the existence of lower cones of non integral dimension. After giving some ‘natural’
examples of sequences of effective dimension 0, we prove that every effectively closed
ωsetA ⊆ 2 of positive Hausdorff admits a computable, surjective mapping
ωA→ 2 .
Wegoontostudythecomplexinterrelationbetweenalgorithmicentropy,randomness,
effectiveHausdorffdimension,andreducibilitymoreclosely. Forthispurposewegeneral
ize effective Hausdorff dimension by introducing the notion of strong effective Hausdorff
measure0. WeareabletoshowthatnothavingstrongeffectiveHausdorffmeasure0does
not necessarily allow to compute a Martin L of¨ random sequence, a sequence of highest
possiblealgorithmicentropy. Besides,weshowthatageneralizationofthenotionofeffec
tive randomness to noncomputable measures yields a very coarse concept of randomness
inthesensethateverynoncomputablesequenceisrandomwithrespecttosomemeasure.
Next,weintroduceSchnorrdimension,anotionofdimensionwhichisalgorithmically
morerestrictivethaneffectivedimension. WeproveamachinecharacterizationofSchnorr
dimension and show that, on the computably enumerable sets, Schnorr Hausdorff dimen
sion and Schnorr packing dimension do not coincide, in contrast to the case of effective
dimension.
WealsostudysubrecursivenotionsofeffectiveHausdorffdimension. Usingresource
bounded martingales, we are able to transfer the use of r expansiveness to the case, which enables us to show that the Small Span Theorem does not hold fordimensioninexponentialtimeE.
Finally, we investigate the effective Hausdorff dimension of sequences against which
no computable nonmonotonic betting strategy can succeed. Computable nonmonotonic
bettinggamesareageneralizationofcomputablemartingales,anditisamajoropenques
tion whether the randomness notion induced by them is equivalent to Martin L of¨ random
ness. Weareabletoshowthatthesequenceswhicharerandomwithrespecttocomputable
nonmonotonic betting games have effective Hausdorff dimension 1, which implies that,
from the viewpoint of algorithmic entropy, they are rather close to Martin L of¨ random
ness.meinemVater

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.