La calculabilité est centrée autour de la notion de fonction calculable telle que définie par Church, Kleene, Rosser et Turing au siècle dernier. D'abord focalisée sur les nombres entiers, la calculabilité a été généralisée aux ensembles, notamment par le biais de la théorie axiomatique des ensembles de Kripke-Platek. Dans cette thèse, nous définissons une notion générale de calculabilité, les sous-calculabilités, dont les axiomes sont satisfaits à la fois par de nombreux fragments récursifs de la calculabilité classique, mais également par des calculabilités d'ordre supérieur sur les ensembles admissibles. Nous montrons, sur cette structure composée d'une énumération de fonctions totales et d'une énumération de fonctions partielles, que les théorèmes classiques de calculabilité (isomorphisme de Myhill, Rogers, théorème s-m-n,point fixe de Kleene, théorème de Rice, créativité, etc.) sont présents sous différentes formes alors même que les sous-calculabilités ne comprennent qu'un fragment des objets de la calculabilité classique. Les structures de degrés associées aux notions de récursivité que nous définissons reflètent également des propriétés de la calculabilité (degrés intermédiaires, high, low, etc.), mais nos réductions étant plus fortes, une structure fine apparaît à l'intérieur même des degrés récursifs. Finalement, nous montrons que les calculabilités sur les admissibles sont interprétables dans le formalisme des sous-calculabilités. En particulier, les énumérations des ensembles alpha-finis et alpha-énumérables présents dans ce contexte nous permettent de transférer certains résultats d'un modèle à l'autre. / Computability is centered on computable functions, as defined by Church, Kleene,Rosser and Turing in the twentieth century. Initially focused on integers,computability has been generalised to sets, in particular thanks toKripke-Platek's Axiomatic Set Theory.In this thesis, we define a general notion of computability,sub-computabilities, whose axioms are satisfied by numerous recursive fragmentsof classical computability, and also by higher-order computabilities overadmissible sets. We show how in sub-computabilities, containing an enumeration oftotal functions and an enumeration of partial functions, classical theoremssuch as Myhill and Rogers isomorphisms, s-m-n theorem, Kleene's fixed-point orRice's theorem hold in a slightly different way, even if a large part ofthe objects of computability are missing. Along with each of thesesub-computabilities and their different notions of recursivity comes a structureof degrees (with intermediate, high and low degrees, etc.), refining theclassical one, our notions of recursivity being stronger.Moreover, we show how admissible computability can be interpreted through theformalism of sub-computabilities. In particular, the enumerations ofalpha-finite and alpha-enumerable sets present in this setting allowsome interesting results to be carried from one model to the other.

The present thesis is dedicated to two topics in Dynamics of Holomorphic maps. The first topic is dynamics of simple parabolic germs at the origin. The second topic is Polynomial-time Computability of Julia sets.\\ Dynamics of simple parabolic germs. Let $F$ be a germ with a simple parabolic fixed point at the origin: $F(w)=w+w^2+O(w^3).$ It is convenient to apply the change of coordinates $z=-1/w$ and consider the germ at infinity $$f(z)=-1/F(-1/z)=z+1+O(z^{-1}).$$ The dynamics of a germ $f$ can be described using Fatou coordinates. Fatou coordinates are analytic solutions of the equation $\phi(f(z))=\phi(z)+1.$ This equation has a formal solution \[\tilde\phi(z)=\text{const}+z+A\log z+\sum_{j=1}^\infty b_jz^{-j},\] where $\sum b_jz^{-j}$ is a divergent power series. Using \'Ecalle's Resurgence Theory we show that $\tilde$ can be interpreted as the asymptotic expansion of the Fatou coordinates at infinity. Moreover, the Fatou coordinates can be obtained from $\tilde \phi$ using Borel-Laplace summation. J.~\'Ecalle and S.~Voronin independently constructed a complete set of invariants of analytic conjugacy classes of germs with a parabolic fixed point. We give a new proof of validity of \'Ecalle's construction. \\ Computability of Julia sets. Informally, a compact subset of the complex plane is called \emph if it can be visualized on a computer screen with an arbitrarily high precision. One of the natural open questions of computational complexity of Julia sets is how large is the class of rational functions (in a sense of Lebesgue measure on the parameter space) whose Julia set can be computed in a polynomial time. The main result of Chapter II is the following: Theorem. Let $f$ be a rational function of degree $d\ge 2$. Assume that for each critical point $c\in J_f$ the $\omega$-limit set $\omega(c)$ does not contain either a critical point or a parabolic periodic point of $f$. Then the Julia set $J_f$ is computable in a polynomial time.

No description available.

No description available.

The present thesis is dedicated to two topics in Dynamics of Holomorphic maps. The first topic is dynamics of simple parabolic germs at the origin. The second topic is Polynomial-time Computability of Julia sets.\\ Dynamics of simple parabolic germs. Let $F$ be a germ with a simple parabolic fixed point at the origin: $F(w)=w+w^2+O(w^3).$ It is convenient to apply the change of coordinates $z=-1/w$ and consider the germ at infinity $$f(z)=-1/F(-1/z)=z+1+O(z^{-1}).$$ The dynamics of a germ $f$ can be described using Fatou coordinates. Fatou coordinates are analytic solutions of the equation $\phi(f(z))=\phi(z)+1.$ This equation has a formal solution \[\tilde\phi(z)=\text{const}+z+A\log z+\sum_{j=1}^\infty b_jz^{-j},\] where $\sum b_jz^{-j}$ is a divergent power series. Using \'Ecalle's Resurgence Theory we show that $\tilde$ can be interpreted as the asymptotic expansion of the Fatou coordinates at infinity. Moreover, the Fatou coordinates can be obtained from $\tilde \phi$ using Borel-Laplace summation. J.~\'Ecalle and S.~Voronin independently constructed a complete set of invariants of analytic conjugacy classes of germs with a parabolic fixed point. We give a new proof of validity of \'Ecalle's construction. \\ Computability of Julia sets. Informally, a compact subset of the complex plane is called \emph if it can be visualized on a computer screen with an arbitrarily high precision. One of the natural open questions of computational complexity of Julia sets is how large is the class of rational functions (in a sense of Lebesgue measure on the parameter space) whose Julia set can be computed in a polynomial time. The main result of Chapter II is the following: Theorem. Let $f$ be a rational function of degree $d\ge 2$. Assume that for each critical point $c\in J_f$ the $\omega$-limit set $\omega(c)$ does not contain either a critical point or a parabolic periodic point of $f$. Then the Julia set $J_f$ is computable in a polynomial time.

Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-14T17:27:49Z (GMT). No. of bitstreams: 1 Agudelo_JuanCarlosAgudelo_D.pdf: 1223911 bytes, checksum: 92e4a3e06e1921aefd3476374d0726f2 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho levantamos, e investigamos do ponto de vista conceitual, evidências de que a complexidade algorítmica pode ser vista como relativa à lógica. Propomos, para tanto, novos modelos de computação fundados sobre lógicas não-clássicas, estudando suas características quanto à expressabilidade computacional e eficiência. A partir desta visão, sugerimos um novo caminho para estudar a eficiência dos modelos de computação quântica, enfatizando a análise de uma lógica subjacente a tais modelos. O conteúdo da tese está estruturado da seguinte maneira: no primeiro capítulo apresentamos uma análise conceitual da noção de 'computação', indicando como este conceito tem mudado desde os trabalhos fundacionais da década de 1930, e discutindo se o conceito deve ser considerado como puramente físico, puramente lógicomatemático ou uma combinação de ambos. O Capítulo 2 introduz duas versões de 'máquinas de Turing paraconsistentes', usando sistemas lógicos diferentes e obtendo modelos com diferentes poderes computacionais (quanto à eficiência); tal resultado constitui uma primeira evidência a favor da relatividade lógica da computação que queremos defender. Outra evidência na mesma direção é apresentada no Capitulo 3, através da generalização dos circuitos booleanos para lógicas não-clássicas, em particular para a lógica paraconsistente mbC e para a lógica modal S5, e da análise do poder computacional de tais generalizações. O Capítulo 4 consiste numa introdução à computação quântica, para logo (no Capítulo 5) estabelecer algumas relações entre modelos de computação quântica e modelos de computação paraconsistente, de maneira a propor uma interpretação lógica dos modelos quânticos. No capítulo final (Capítulo 6) descrevemos várias relações entre mecânica quântica e lógica paraix consistente, relações estas que sugerem potencialidades com alto grau de relevância a respeito da abordagem paraconsistente dos fenômenos computacionais quânticos e que incitam a continuar explorando esta alternativa. / Abstract: This work provides evidences to view computational complexity as logic-relative, by introducing new models of computation through non-classical logics and by studying their features with respect to computational expressivity and efficiency. From this point of view, we suggest a new way to study the efficiency of quantum computational models consisting in the analysis of an underlying logic. The contents of the thesis is structured in the following way: the first chapter presents a conceptual analysis of the notion of 'computation', showing how this concept evolved since the decade of 1930 and discussing whether it can be considered a pure physical or a pure logic-mathematical concept, or a combination of both paradigms. Chapter 2 introduces two versions of 'paraconsistent Turing machines', by considering different logic systems and obtaining models with different computational capabilities (with respect to efficiency); such a result constitute a first evidence in favor of the logical relativity of computation that we are defending here. Another evidence in the same direction is presented in Chapter 3 through a generalization of boolean circuits to non-classical logics, particularly for the paraconsistent logic mbC and for the modal logic S5, and by analyzing the computational power of such generalizations. Chapter 4 consists in an introduction to quantum computation. This is used in Chapter 5 to establish some relationships between quantum and paraconsistent models of computation, in order to propose a logic interpretation of quantum models. The final chapter (Chapter 6) describes several connections between quantum mechanics and paraconsistent logic; such relationship suggests highly relevant potentialities in favor of the paraconsistent approach to quantum computation phenomena encouraging to continue exploring this alternative. / Doutorado / Logica / Doutor em Filosofia

The concept of a recursive function has been extensively studied using traditional tools of computability theory. However, with the development of category-theoretic methods it has become possible to study recursion in a more general (abstract) sense. The particular model this thesis is structured around is known as a Turing category. The structure within a Turing category models the notion of partiality as well as recursive computation, and equips us with the tools of category theory to study these concepts. The goal of this work is to build a formal language description of this computation model. Specifically, to use the Coq proof assistant to formulate informal definitions, propositions and proofs pertaining to Turing categories in the underlying formal language of Coq, the Calculus of Co-inductive Constructions (CIC). Furthermore, we have instantiated the more general Turing category formalism with a CIC description of the category which models the language of partial recursive functions exactly.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20883号 / 理博第4335号 / 新制||理||1623(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 西村 進, 教授 上 正明, 教授 長谷川 真人 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

<p>Collecting user data is crucial for advancing machine learning, social science, and government policies, but the privacy of the users whose data is being collected is a growing concern. {\em Differential Privacy (DP)} has emerged as the most standard notion for privacy protection with robust mathematical guarantees. Analyzing such massive amounts of data in a privacy-preserving manner motivates the need to study differentially-private algorithms that are also super-efficient.  </p> <p><br></p> <p>This thesis initiates a systematic study of differentially-private sublinear-time and sublinear-space algorithms. The contributions of this thesis are two-fold. First, we design some of the first differentially private sublinear algorithms for many fundamental problems. Second, we develop general DP techniques for designing differentially-private sublinear algorithms. </p> <p><br></p> <p>We give the first DP sublinear algorithm for clustering by generalizing a subsampling framework from the non-DP sublinear-time literature. We give the first DP sublinear algorithm for estimating the maximum matching size. Our DP sublinear algorithm for estimating the average degree of the graph achieves a better approximation than previous works. We give the first DP algorithm for releasing $L_2$-heavy hitters in the sliding window model and a pure $L_1$-heavy hitter algorithm in the same model, which improves upon previous works.  </p> <p><br></p> <p>We develop general techniques that address the challenges of designing sublinear DP algorithms. First, we introduce the concept of Coupled Global Sensitivity (CGS). Intuitively, the CGS of a randomized algorithm generalizes the classical  notion of global sensitivity of a function, by considering a coupling of the random coins of the algorithm when run on neighboring inputs. We show that one can achieve pure DP by adding Laplace noise proportional to the CGS of an algorithm. Second, we give a black box DP transformation for a specific class of approximation algorithms. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function has small global sensitivity. In particular, this transformation gives rise to sublinear DP algorithms for many problems, including triangle counting, the weight of the minimum spanning tree, and norm estimation.</p>

Whereas early researchers in computability theory described effective computability in terms of such models as Turing machines, Markov algorithms, and register machines, a recent trend has been to use simple programming languages as computability models. A parallel development to this programming approach to computability theory is the current interest in systematic and scientific development and proof of programs. This paper investigates the feasibility of using formal proofs of programs in computability theory. After describing a framework for formal verification of programs written in a simple theoretical programming language, we discuss the proofs of several typical programs used in computability theory.