Made available in DSpace on 2014-12-17T15:47:45Z (GMT). No. of bitstreams: 1 AaraoL.pdf: 741847 bytes, checksum: 45403e29cc4bf1b00b42e5221478dc54 (MD5) Previous issue date: 2006-05-19 / A matem?tica intervalar ? uma teoria matem?tica originada na d?cada de 60 com o objetivo de responder quest?es de exatid?o e efici?ncia que surgem na pr?tica da computa??o cient?fica e na resolu??o de problemas num?ricos. As abordagens cl?ssicas para teoria da computabilidade tratam com problemas discretos (por exemplo, sobre os n?meros naturais, n?meros inteiros, strings sobre um alfabeto finito, grafos, etc.). No entanto, campos da matem?tica pura e aplicada tratam com problemas envolvendo n?meros reais e n?meros complexos. Isto acontece, por exemplo, em an?lise num?rica, sistemas din?micos, geometria computacional e teoria da otimiza??o. Assim, uma abordagem computacional para problemas cont?nuos ? desej?vel, ou ainda necess?ria, para tratar formalmente com computa??es anal?gicas e computa??es cient?ficas em geral. Na literatura existem diferentes abordagens para a computabilidade nos n?meros reais, mas, uma importante diferen?a entre estas abordagens est? na maneira como ? representado o n?mero real. Existem basicamente duas linhas de estudo da computabilidade no cont?nuo. Na primeira delas uma aproxima??o da sa?da com precis?o arbitr?ria ? computada a partir de uma aproxima??o razo?vel da entrada [Bra95]. A outra linha de pesquisa para computabilidade real foi desenvolvida por Blum, Shub e Smale [BSS89]. Nesta aproxima??o, as chamadas m?quinas BSS, um n?mero real ? visto como uma entidade acabada e as fun??es comput?veis s?o geradas a partir de uma classe de fun??es b?sicas (numa maneira similar ?s fun??es parciais recursivas). Nesta disserta??o estudaremos o modelo BSS, usado para se caracterizar uma teoria da computabilidade sobre os n?meros reais e estenderemos este para se modelar a computabilidade no espa?o dos intervalos reais. Assim, aqui veremos uma aproxima??o para computabilidade intervalar epistemologicamente diferente da estudada por Bedregal e Aci?ly [Bed96, BA97a, BA97b], na qual um intervalo real ? visto como o limite de intervalos racionais, e a computabilidade de uma fun??o intervalar real depende da computabilidade de uma fun??o sobre os intervalos racionais

Les sous-décalages sont des ensembles de coloriages d'un groupe définis en excluant certains motifs, et munis d'une action de décalage. Ces objets apparaissent naturellement comme discrétisations de systèmes dynamiques : à partir d'une partition de l'espace, on associe à chaque point de ce-dernier la suite des partitions visitées sous l'action du système.Plusieurs résultats récents ont mis en évidence la riche interaction entre la dynamique des sous-décalages et leur propriétés algorithmiques. Un exemple remarquable est la classification des entropies des sous-décalages multidimensionnels de type fini comme l'ensemble des nombres récursivement énumérables à droite. Cette thèse s'intéresse aux sous-décalages avec une approche double : d'un côté on s'intéresse à leurs propriétés dynamiques et de l'autre on les étudie comme des modèles de calcul.Cette thèse contient plusieurs résultats : une condition combinatoire suffisante prouvant qu'un sous-décalage dans un groupe dénombrable est non-vide, un théorème de simulation qui réalise une action effective d'un groupe de type fini comme un facteur d'une sous-action d'un sous-décalage de type fini, une caractérisation de l'effectivité à l'aide de machines de Turing généralisées et l'indécidabilité du problème de torsion pour deux groupes, qui sont invariants de systèmes dynamiques.Comme corollaires de nos résultats, nous obtenons d'abord une preuve courte de l'existence de sous-décalages fortement apériodiques sur tout groupe dénombrable. Puis, dans le cas d'un produit semi-direct de la grille bidimensionnelle avec un groupe de type fini avec problème du mot décidable, nous montrons que le sous-décalage obtenu est de type fini. / Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.Severa! breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the ether hand we studythese abjects as computational models.Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a d-dimensional integer lattice with a finitely generated group with decida ble word problem whenever d> 1.

Investigamos algumas capacidades computacionais de sistemas constituídos de mapas acoplados. Particularmente, exploramos o uso desses sistemas no tratamento de três problemas: a identificação de simetria de reflexão em imagens planas; a formação de clusters de elementos síncronos em redes com topologias do tipo small-worlds; e a construção de figuras que obedecem a uma regra de composição. Para a identificação de simetria, motivados por modelos biológicos construímos uma rede de mapas em que, acoplamentos locais e globais permitem verificar a simetria de reflexão de uma imagem plana através do sincronismo dos elementos do sistema. Em particular, esse sistema apresenta a habilidade de não requerer sua reinicialização para novas identificações e permite, assim, a identificação de simetrias em cenas que se modificam no tempo. Sistemas estendidos de mapas acoplados são, em geral, construídos conectando-se todos os elementos ou pela formação de uma malha uniforme de conexões. A dinâmica desses sistemas pode apresentar a formação de grupos de elementos síncronos. Esse comportamento de auto-organização pode ser encontrado em diversos sistemas complexos reais que, entretanto e mais comumente, exibem topologias de conexões não uniformes entre seus elementos. Mostramos aqui, a capacidade de mapas acoplados, em diferentes topologias de small-worlds, exibirem a formação de grupos de elementos síncronos com um número de conexões próximo ao das malhas com acoplamento local mas com uma significativa redução da distância média entre os elementos da rede. Por último consideramos o uso de sistemas de mapas como sistemas programáveis. Normalmente, para formação de padrões e figuras no plano, sistemas de funções iteradas são empregados com um conjunto fixo de contrações lineares no plano. Aqui, mostramos a possibilidade do uso de mapas mais gerais na produção de tais padrões e figuras, incluindo estruturas biológicas e fractais. Funções de troca são empregadas para alterar a dinâmica do sistema segundo ou o contexto ou o estado, e fornecem, desse modo, uma forma de programação. / We investigated some computational abilities of systems composed by coupled maps. Here, we explored the use of those systems in dealing with three problems: the identification of reflection symmetry in bidimensional images; the appearing of clusters of synchronous elements in networks with small-worlds topologies; and in constructing figures obeying a composition rule. For the symmetry identification problem, we were motivated by biological models to built a network of coupled maps, with local and global couplings, that verify reflection symmetry of plane images through the synchronism of the elements from the system. In matter, this system presents the ability to perform a new identification without re-initializing the system. This feature allows the identification of symmetries in scenes that can change during the time. In general extended coupled map systems have all elements connected, or the connections lying over a uniform lattice. The dynamics of these systems can present the formation of clusters with synchronous elements. Such auto-organization behavior can be found in several actual complex systems. However, more commonly, these systems do not exhibit uniform connections among their elements. Here, we investigated the capacity of coupled map systems, in different topologies of small-worlds, exhibiting the formation of clusters with synchronous elements, by using a number of connections close to the number in regular lattices but with a significant reduction of the mean distance among their elements. Last we considered the use of systems of maps as programmable systems. Usually, for formation of patterns and geometric figures in the plan, iterated function systems work with a fixed set of linear contractions in the plan. Here, we showed that is possible to use more general maps to the production of patterns and geometric figures, and biological patterns and fractals are generated. Shift functions are used to change the dynamics of the map system due to either the context or the state, giving a way of programming the system.

Durant ces dernières décennies, la communauté informatique a montré un intérêt grandissant pour les modèles de calcul non-standard, inspirés par des phénomènes physiques, biologiques ou chimiques. Les propriétés exactes de ces modèles ont parfois été l'objet de controverses: que calculent-ils? Et à quelle vitesse? Les enjeux de ces questions sont renforcés par la possibilité que certains de ces modèles pourraient transgresser les limites acceptées du calcul, en violant soit la thèse de Church-Turing soit la thèse de Church-Turing étendue. La possibilité de réaliser physiquement ces modèles a notamment été au coeur des débats. Ainsi, des considérations empiriques semblent introduites dans les fondements même de la calculabilité et de la complexité computationnelle, deux théories qui auraient été précédemment considérées comme des parties purement a priori de la logique et de l'informatique. Par conséquent, ce travail est consacré à la question suivante : les limites du calcul reposent-elles sur des fondements empiriques? Et si oui, quels sont-ils? Pour ce faire, nous examinons tout d'abord la signification précise des limites du calcul, et articulons une conception épistémique du calcul, permettant la comparaison des modèles les plus variés. Nous répondrons à la première question par l'affirmative, grâce à un examen détaillé des débats entourant la faisabilité des modèles non-standard. Enfin, nous montrerons les incertitudes entourant la deuxième question dans l'état actuel de la recherche, en montrant les difficultés de la traduction des concepts computationnels en limites physiques. / Recent years have seen a surge in the interest for non-standard computational models, inspired by physical, biological or chemical phenomena. The exact properties of some of these models have been a topic of somewhat heated discussion: what do they compute? And how fast do they compute? The stakes of these questions were heightened by the claim that these models would violate the accepted limits of computation, by violating the Church-Turing Thesis or the Extended Church-Turing Thesis. To answer these questions, the physical realizability of some of those models - or lack thereof - has often been put at the center of the argument. It thus seems that empirical considerations have been introduced into the very foundations of computability and computational complexity theory, both subjects that would have been previously considered purely a priori parts of logic and computer science. Consequently, this dissertation is dedicated to the following question: do computability and computational complexity theory rest on empirical foundations? If yes, what are these foundations? We will first examine the precise meaning of those limits of computation, and articulate a philosophical conception of computation able to make sense of this variety of models. We then answer the first question by the affirmative, through a careful examination of current debates around non-standard models. We show the various difficulties surrounding the second question, and study how they stem from the complex translation of computational concepts into physical limitations.

Gegenstand dieser Dissertation ist eine umfassende Analyse der Stabilität von Asteroidenbahnen im Edgeworth-Kuiper-Gürtel am Beispiel der 3:5-, 4:7- und der 1:2-Bahnresonanz mit Neptun. Einen weiteren Schwerpunkt der Arbeit bildet die Untersuchung der numerischen Berechenbarkeit der Lyapunov-Zeit von Asteroidenbahnen. Ausgehend von einer allgemeinen Beschreibung der bei numerischen Berechnungen auftretenden Rundungs- und Diskretisierungsfehler wird deren Wachstum bei numerischen Integrationen ermittelt. Diese, teilweise maschinenabhängigen, Fehler beeinflussen die berechnete Trajektorie des Asteroiden ebenso wie die daraus abgeleitete Lyapunov-Zeit. Durch Beispielrechnungen mit unterschiedlichen Rechnerarchitekturen und Integrationsmethoden wird der Einfluss auf die erhaltenen Lyapunov-Zeiten eingehend untersucht. Als Maß zur Beschreibung dieser Abhängigkeit wird ein Berechenbarkeitsindex $\kappa$ definiert. Weiterhin wird gezeigt, dass die allgemeine Struktur des Phasenraumes robust gegenüber diesen Änderungen ist. Unter Nutzung dieser Erkenntnis werden anschließend ausgewählte Bahnresonanzen im Edgeworth-Kuiper-Gürtel untersucht. Grundlegende Charakteristika, wie die Resonanzbreiten, werden dabei aus einfachen Modellen abgeleitet. Eine möglichst realitätsnahe Beschreibung der Stabilität wird durch numerische Integration einer Vielzahl von Testkörpern zusammen mit den Planeten Jupiter bis Neptun erreicht. Die erhaltenen Ergebnisse werden dabei mit der beobachteten Verteilung der Asteroiden im Edgeworth-Kuiper-Gürtel verglichen. ---- Hinweis: Beim Betrachten der pdf-Version dieses Dokumentes mit dem Acrobat Reader mit einer Version kleiner 8.0 kann es unter Windows zu Problemen in der Darstellung der Abbildungen auf den Seiten 46, 72, 74, 79 und 86 kommen. Um die Datenpunkte zu sehen ist eine Vergrößerung von mehr als 800% notwendig. Alternativ kann in den Grundeinstellungen der Haken für das Glätten von Vektorgraphiken entfernt werden. / This dissertation presents a comprehensive description of the stability of asteroid orbits in the Edgeworth-Kuiper belt taking the 3:5, 4:7 and 1:2 mean motion resonance with Neptune as example. Further emphasis is given to the numerical computability of the Lyapunov time of asteroids. Starting with a general description of rounding and approximation errors in numerical computations, the growth of these errors within numerical integrations is estimated. These, partly machine-dependent errors influence the calculated trajectory of the asteroid as well as the derived Lyapunov time. Different hardware architectures and integration methods were used to investigate the influence on the computed Lyapunov time. As a measure of this dependence a computability index $\kappa$ is defined. Furthermore it is shown, that the general structure of phase space is robust against these changes. Subsequently, several selected mean motion resonances in the Edgeworth-Kuiper belt are investigated using these findings. Basic properties, like the resonance width, are deduced from simple models. To get a realistic description of the stability, a huge number of test particles was numerically integrated together with the planets Jupiter to Neptune. The obtained results are compared to the observed distribution of asteroids in the Edgeworth-Kuiper belt. ---- Additional information: If the pdf-file of this document is viewed using Acrobat Reader with a version less 8.0 under Windows the figures on page 46, 72, 74, 79 and 86 are shown incomplete. To see the data points a zoom factor larger than 800% is necessary. Alternatively the smoothing of vector graphics should be disabled in the settings of the reader.

L'objet de cette thèse est l'étude de l'auto-organisation dans les automates cellulaires unidimensionnels.Les automates cellulaires sont un système dynamique discret ainsi qu'un modèle de calcul massivement parallèle, ces deux aspects s'influençant mutuellement. L'auto-organisation est un phénomène où un comportement organisé est observé asymptotiquement, indépendamment de la configuration initiale. Typiquement, nous considérons que le point initial est tiré aléatoirement: étant donnée une mesure de probabilité décrivant une distribution de configurations initiales, nous étudions son évolution sous l'action de l'automate, le comportement asymptotique étant décrit par la(les) mesure(s) limite(s).Notre étude présente deux aspects. D'abord, nous caractérisons les mesures qui peuvent être atteintes à la limite par les automates cellulaires; ceci correspond aux différents comportements asymptotiques pouvant apparaître en simulation. Cette approche rejoint divers résultats récents caractérisant des paramètres de systèmes dynamiques par des conditions de calculabilité, utilisant des outils d'analyse calculable. Il s'agit également d'une description de la puissance de calcul des automates cellulaires sur les mesures.Ensuite, nous proposons des outils pour létude de l'auto-organisation dans des classes restreintes. Nous introduisons un cadre d'étude d'automates pouvant être vus comme un ensemble de particules en interaction, afin d'en déduire des propriétés sur leur comportement asymptotique. Une dernière direction de recherche concerne les automates convergeant vers la mesure uniforme sur une large classe de mesures initiales (phénomène de randomisation). / The subject of this thesis is the study of self-organization in one-dimensional cellular automata.Cellular automata are a discrete dynamical system as well as a massively parallel model of computation, both theseaspects influencing each other. Self-organisation is a phenomenon where an organised behaviour is observed asymptotically, regardless of the initial configuration. Typically, we consider that the initial point is sampled at random; that is, we consider a probability measure describing the distribution of theinitial configurations, and we study its evolution under the action of the automaton, the asymptoticbehaviour being described by the limit measure(s).Our work is two-sided. On the one hand, we characterise measures that can bereached as limit measures by cellular automata; this corresponds to the possible kinds of asymptoticbehaviours that can arise in simulations. This approach is similar to several recent results characterising someparameters of dynamical systems by computability conditions, using tools from computable analysis. Thisresult is also a description of the measure-theoretical computational power of cellular automata.On the other hand, we provided tools for the practical study of self-organization in restricted classes of cellularautomata. We introduced a frameworkfor cellular automata that can be seen as a set of interacting particles, in order todeduce properties concerning their asymptotic behaviour. Another ongoing research direction focus on cellular automata that converge to the uniform measurefor a wide class of initial measures (randomization phenomenon).

Gegenstand dieser Dissertation ist eine umfassende Analyse der Stabilität von Asteroidenbahnen im Edgeworth-Kuiper-Gürtel am Beispiel der 3:5-, 4:7- und der 1:2-Bahnresonanz mit Neptun. Einen weiteren Schwerpunkt der Arbeit bildet die Untersuchung der numerischen Berechenbarkeit der Lyapunov-Zeit von Asteroidenbahnen. Ausgehend von einer allgemeinen Beschreibung der bei numerischen Berechnungen auftretenden Rundungs- und Diskretisierungsfehler wird deren Wachstum bei numerischen Integrationen ermittelt. Diese, teilweise maschinenabhängigen, Fehler beeinflussen die berechnete Trajektorie des Asteroiden ebenso wie die daraus abgeleitete Lyapunov-Zeit. Durch Beispielrechnungen mit unterschiedlichen Rechnerarchitekturen und Integrationsmethoden wird der Einfluss auf die erhaltenen Lyapunov-Zeiten eingehend untersucht. Als Maß zur Beschreibung dieser Abhängigkeit wird ein Berechenbarkeitsindex $\kappa$ definiert. Weiterhin wird gezeigt, dass die allgemeine Struktur des Phasenraumes robust gegenüber diesen Änderungen ist. Unter Nutzung dieser Erkenntnis werden anschließend ausgewählte Bahnresonanzen im Edgeworth-Kuiper-Gürtel untersucht. Grundlegende Charakteristika, wie die Resonanzbreiten, werden dabei aus einfachen Modellen abgeleitet. Eine möglichst realitätsnahe Beschreibung der Stabilität wird durch numerische Integration einer Vielzahl von Testkörpern zusammen mit den Planeten Jupiter bis Neptun erreicht. Die erhaltenen Ergebnisse werden dabei mit der beobachteten Verteilung der Asteroiden im Edgeworth-Kuiper-Gürtel verglichen. ---- Hinweis: Beim Betrachten der pdf-Version dieses Dokumentes mit dem Acrobat Reader mit einer Version kleiner 8.0 kann es unter Windows zu Problemen in der Darstellung der Abbildungen auf den Seiten 46, 72, 74, 79 und 86 kommen. Um die Datenpunkte zu sehen ist eine Vergrößerung von mehr als 800% notwendig. Alternativ kann in den Grundeinstellungen der Haken für das Glätten von Vektorgraphiken entfernt werden. / This dissertation presents a comprehensive description of the stability of asteroid orbits in the Edgeworth-Kuiper belt taking the 3:5, 4:7 and 1:2 mean motion resonance with Neptune as example. Further emphasis is given to the numerical computability of the Lyapunov time of asteroids. Starting with a general description of rounding and approximation errors in numerical computations, the growth of these errors within numerical integrations is estimated. These, partly machine-dependent errors influence the calculated trajectory of the asteroid as well as the derived Lyapunov time. Different hardware architectures and integration methods were used to investigate the influence on the computed Lyapunov time. As a measure of this dependence a computability index $\kappa$ is defined. Furthermore it is shown, that the general structure of phase space is robust against these changes. Subsequently, several selected mean motion resonances in the Edgeworth-Kuiper belt are investigated using these findings. Basic properties, like the resonance width, are deduced from simple models. To get a realistic description of the stability, a huge number of test particles was numerically integrated together with the planets Jupiter to Neptune. The obtained results are compared to the observed distribution of asteroids in the Edgeworth-Kuiper belt. ---- Additional information: If the pdf-file of this document is viewed using Acrobat Reader with a version less 8.0 under Windows the figures on page 46, 72, 74, 79 and 86 are shown incomplete. To see the data points a zoom factor larger than 800% is necessary. Alternatively the smoothing of vector graphics should be disabled in the settings of the reader.

Wir schlagen eine praxisorientierte Explikation der philosophischen Position des Mathematischen Pluralismus vor. Dieser Position zufolge existieren mehr als ein legitimes mathematisches System. Wir interpretieren 'legitim' als 'geeignet zur Realisierung wissenschaftlicher Ziele' und wenden die resultierende pluralistische Position auf die Mathematische Ökonomie an. Wir präsentieren ein begriffliches Rahmenwerk, in dem pluralistische Thesen formuliert und evaluiert werden können, stellen ein informelles System der Konstruktiven Mathematik als Alternative zur Klassischen Mathematik vor, und zeigen, dass verschiedene ökonomische Theoreme nicht konstruktiv beweisbar sind. Auf dieser Basis argumentieren wir, dass Pluralismus relativ zu Zielen mit Bezug zu Erklärung und Simplizität in der Ökonomie vorliegt. / We propose a practice-oriented explication of the philosophical position known as mathematical pluralism. According to this position there exist more than one legitimate mathematical system. We interpret 'legitimate' as 'suitable for realizing scientific goals' and apply the resultant pluralist position to mathematical economics. We present a conceptual framework within which pluralist theses can be formulated and evaluated, introduce an informal system of constructive mathematics as an alternative to classical mathematics, and point out that central theorems of economic equilibrium theory are not constructively provable. On this basis, we argue that pluralism obtains with respect to goals related to explanation and simplicity in economics.