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.

For a uniquely defined subset of phase space, solutions of non-linear, coupled reaction-diffusion equations may converge to heterogeneous steady states, organic in appearance. Hence, many theoretical models for pattern formation, as in the theory of morphogenesis, include the mechanics of reaction-diffusion equations. The standard method of simulation for such pattern formation models does not facilitate reproducibility of results, or the verification of convergence to a solution of the problem via the method of mesh refinement. In this thesis we explore a new methodology circumventing the aforementioned issues, which is independent of the choice of programming language. While the new method allows more control over solutions, the user is required to make more choices, which may or may not have a determining effect on the nature of resulting patterns. In an attempt to quantify the extent of the possible effects, we study heterogeneous steady states for two well known reaction-diffusion models, the Gierer-Meinhardt model and the Schnakenberg model. / Alexander Graham Bell Canada Graduate Scholarship provides financial support to high calibre scholars who are engaged in master's or doctoral programs in the natural sciences or engineering. / Natural Sciences and Engineering Research Council of Canada

Orientador: Walter Alexandre Carnielli / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas / Made available in DSpace on 2018-08-17T17:02:46Z (GMT). No. of bitstreams: 1 Araujo_Anderson_D.pdf: 1286485 bytes, checksum: 1e51db7a5721f4affeaf8f512d23269e (MD5) Previous issue date: 2011 / Resumo: Esta tese propõe uma nova abordagem da computabilidade de Turing clássica, denominada abordagem modelo-teórica. De acordo com essa abordagem, estruturas e teorias são associadas às máquinas de Turing a fim de investigar as características de suas computações. Uma abordagem modelo-teórica da computabilidade de Turing através da lógica de primeira ordem é desenvolvida, e resultados de correspondência, correção, representação e completude entre máquinas, estruturas e teorias de Turing são demonstrados. Nessa direção, os resultados obtidos a respeito de propriedades tais como estabilidade, absoluticidade, universalidade e logicidade enfatizam as potencialidades da computabilidade modelo-teórica de primeira ordem. Demonstra-se que a lógica subjacente às teorias de Turing é uma lógica minimal intuicio-nista, sendo capaz, inclusive, de internalizar um operador de negação clássico. As técnicas formuladas nesta tese permitem, sobretudo, investigar a computabilidade de Turing em modelos não-padrão da aritmética. Nesse contexto, uma nova perspectiva acerca do fenômeno de Tennenbaum e uma avaliação crítica da abordagem de Dershowitz e Gurevich da tese de Church-Turing sào apresentadas. Como conseqüência, postula-se um princípio de interna-lidade aritmética na computabilidade, segundo o qual o próprio conceito de computação é relativo ao modelo aritmético em que as máquinas de Turing operam. Assim, a tese unifica as caracterizações modelo-aritméticas do problema P versus NP existentes na literatura, revelando, por fim, uma barreira modelo-aritmética para a possibilidade de solução desse problema central em complexidade computacional no que diz respeito a certos métodos. Em sua totalidade, a tese sustenta que características cruciais do conceito de computação podem ser vislumbradas a partir da dualidade entre finitude e infinitude presente na distinção entre números naturais padrão e não-padrão / Abstract: This PhD thesis proposes a new approach to classical Turing computability, called a model-theoretic approach. In that approach, structures and theories are associated to Turing machines in order to study the characteristics of their computations. A model-theoretic approach to Turing computability through first-order logic is developed, and first results about correspondence, soundness, representation and completeness among Turing machines, structures and theories are proved. In this line, the results about properties as stability, absoluteness, universality and logicality emphasize the importance of the model-theoretic standpoint. It is shown that the underlying logic of Turing theories is a minimal intuicionistic logic, being able to internalize a classical negation operator. The techniques obtained in the present dissertation permit us to examine the Turing computability over nonstandard models of arithmetic as well. In this context, a new perspective about Tennenbaum's phenomenon and a critical evaluation of Dershowitz and Gurevich's account on Church-Turing's thesis are given. As a consequence, an arithmetic internality principle is postulated, according to which the concept of computation itself is relative to the arithmetic model that Turing machines operate. In this way, the dissertation unifies the existing model-arithmetic characterizations of the P versus NP problem, leading, as a by-product, to a model-arithmetic barrier to the solvability of that central problem in computational complexity with respect to certain techniques. As a whole, the dissertation sustains that crucial characteristics of the concept of computation may be understood from the duality between finiteness and infiniteness inherent within the distinction between standard and nonstandard natural numbers / Doutorado / Filosofia / Doutor em Filosofia

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

Orientador: Marcus Aloizio Martinez de Aguiar / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin / Made available in DSpace on 2018-08-20T00:25:10Z (GMT). No. of bitstreams: 1 Fernandes_LucasDias_M.pdf: 4124571 bytes, checksum: c9eaf6c1371f1023d813ae1f45f3aa27 (MD5) Previous issue date: 2012 / Resumo: Sistemas de reação-difusão podem apresentar, sob certas condições, formação de padrões espaciais heterogêneos estacionários. Chamados padrões de Turing (ou instabilidades de Turing) devido ao trabalho de Alan Turing, sua formulação matemática é importante para o estudo da formação de padrões em geral e desempenha papel central em muitos campos da biologia, tais como ecologia e morfogênese. No presente estudo, focamos no papel exercido pelos padrões de Turing na descrição de distribuições de abundância de espécies de predadores e presas que habitam ambientes fragmentados com estrutura de rede livre de escala, onde as conexões indicam caminhos de dispersão dessas espécies. Para estudar formação de padrões em cadeias tróficas maiores, nós estendemos o modelo de presa-predador original, proposto por Nakao e Mikhailov (Nature Physics, 2010), incluindo pares de presa-predador adicionais. Mostramos que esses sistemas dinâmicos com mais de dois graus de liberdade apresentam não apenas padrões de Turing, mas também transições entre regimes caóticos, sincronizados e estacionários, dependendo dos parâmetros do sistema. Para o caso dos padrões estacionários em uma cadeia trofica com 6 espécies, identificamos distribuições não triviais das presas nos sítios da rede, dependendo da força de acoplamento entre os pares presa-predador, o que sugere que efeitos de competição aparente são importantes nos padrões observados. Nossos resultados sugerem que diferenças nas distribuições de abundância entre fragmentos podem ser, pelo menos em parte, devidos a padrões de Turing auto-organizados, e não necessariamente a heterogeneidades ambientais intrínsecas / Abstract: Reaction-diffusion systems may lead, under certain conditions, to the formation of steady state heterogeneous spatial patterns. Named Turing patterns (or Turing instabilities) after Alan Turing's work, their mathematical formulation is important for the study of pattern formation in general and play central roles in many elds of biology, such as ecology and morphogenesis. In the present study, we focus on the role of Turing patterns in describing the abundance distribution of species distributed in patches in a scale free network structure, connected by diffusion. In order to study pattern formation in larger trophic food webs, we have extended the original prey-predator model proposed by Nakao and Mikhailov (Nature Physics, 2010) by including additional prey-predator pairs. We observed not only Turing patterns, but also transitions between chaotic, synchronized and stationary regimes, depending on the system parameters. In the case of stationary patterns in trophic webs with 6 species, we identified non trivial prey distributions in the networks nodes, depending on the coupling strength between prey-predator pairs, suggesting that effects of apparent competition are important in the observed patterns. Our results suggest that differences in abundance distribution among patches may be, at least in part, due to self organized Turing patterns, and not necessarily to intrinsic environmental heterogeneities / Mestrado / Física / Mestre em Física

Background. In this thesis a novel method of skinning a mesh utilizing Nvidia’sTuring Mesh Shader pipeline is presented. Skinning a mesh is often performed with a Vertex Shader or a Compute Shader. By leveraging the strengths of the new pipeline it may be possible to further optimize the skinning process and increase performance, especially for more complex meshes. Objectives. The aim is to determine if the novel method is a suitable replacement for existing skinning implementations. The key metrics being studied is the total GPU frame time of the novel implementation in relation to the rest, and its total memory usage. Methods. Beyond the pre-existing implementations such as Vertex Shader skinning and Compute Shader skinning, two new methods using Mesh Shaders are implemented. The first implementation being a naive method that simply divides the mesh into meshlets and skins each meshlet in isolation. The proposed novel common influences method instead takes the skinning data, such as the joint influences of each vertex, into account when generating meshlets. The intention is to produce meshlets where all vertices are influenced by the same joints, allowing for information to be moved from a per vertex basis to a per meshlet basis. Allowing for fewer fetches to occur in the shader at run-time and potentially better performance. Results. The results indicate that utilizing Mesh Shaders results in approximately identical performance compared to Vertex Shader skinning, (which was observed to be the fastest of the previous implementations) with the novel implementation being marginally slower due to the increased number of meshlets generated. Mesh Shading has the potential to be faster if optimizations unique to the new shaders are employed. Despite producing more meshlets, the novel implementation is not significantly slower and is faster at processing individual meshlets compared to the naive approach. The novel Common Influences implementation spends between 15-22% less time processing each meshlet at run-time compared to the naive solution. Conclusions. Ultimately the unique capabilities of Mesh Shaders allow for potential performance increases to be had. The proposed novel Common Influences method shows promise due to it being faster on a per meshlet basis, but more work must be done in order to reduce the number of meshlets generated. The Mesh Shading pipeline is as of writing very new and there is a lot of potential for future work to further enhance and optimize the work presented in this thesis. More work must be done in order to make the meshlet generation more efficient so that the run-time workload is reduced as much as possible. / Bakgrund. I denna avhandling presenteras en ny metod för att deformera en modell med hjälp av den nya Mesh Shader funktionaliteten som är tillgänglig i Nvidias nya Turing arkitektur. Deformering av modeller utförs just nu oftast med så kallade Vertex eller Compute Shaders. Genom att nyttja styrkan hos den nya arkitekturen så kan det vara möjligt att ytterligare optimera deformeringsprocessen och på så sätt öka prestandan. Speciellt i samband där mer komplexa modeller används. Syfte. Syftet är att avgöra om den nya metoden är en lämplig ersättning av de nuvarande implementationerna. De viktigaste aspekterna som studeras är den totala GPU-exekveringstiden per bild som renderas av den nya metoden i förhållande till resterande, samt dess totala minnesanvändning. Metod. Utöver de befintliga implementeringarna, såsom Vertex Shader deformering och Compute Shader deformering, implementeras två nya metoder som använder Mesh Shaders. Den första implementeringen är en naiv metod som helt enkelt delar modellen i mindre delar, så kallade meshlets och deformerar varje meshlet i isolering. Den föreslagna nya common influences metoden tar i stället hänsyn till deformeringsdatan som tillhör modellen, såsom de gemensamma inverkningarna av varje vertex, vid generering av meshlets.  Avsikten är att producera meshlets där alla vertriser påverkas av samma leder i modellens skelett, vilket gör det möjligt att flytta informationen från en per vertris basis till en per meshlet basis. Detta tillåter att färre hämtningar sker på grafikkortet vid körning och vilket kan potentiellt ge bättre prestanda. Resultat. Resultaten indikerar att utnyttjandet av Mesh Shaders resulterar i ungefär samma prestanda jämfört med Vertex Shader deformering, (som observerades vara den snabbaste av de existerande implementationerna) samt att den orginella implementationen är marginellt långsammare på grund av ett högre antal meshlets genereras. Mesh Shading har potential till att bli snabbare om optimeringar somär unika till den nya arkitekturen används. Trots att man producerar fler meshlets,är den nya metoden inte markant långsammare och är snabbare med att bearbeta meshlets individuellt jämfört med den naiva implementationen. Den orginella implementationen spenderar mellan 15-22% mindre tid per meshlet vid körtid jämfört med den naiva lösningen. Slutsatser. I slutändan så erbjuder Mesh Shaders unika nya möjligheter till optimeringar som kan leda till potentiellt bättre prestanda. Den föreslagna nya Common Influences-metoden är lovande på grund av att den är snabbare per meshlet, men mer arbete måste utföras för att minska antalet genererade meshlets. Mash Shaders och Turing arkitekturen är vid skrivande stund fortfarande väldigt nya och det finns mycket potential för framtida arbeten att yterrligare förbättra och optimera det arbete som presenteras i denna avhandling. Mer arbete måste utföras för att göra meshletgenereringen effektivare så att arbetet som måste utföras under körtid minskas så mycket som möjligt.

Call number: LD2668 .T4 1962 C44

This practice‐based research is a long creative work about Alan Turing. It consists of a series that includes prose, narrative poems and visual poems. An accompanying critical commentary, which is split into three sections, addresses the relationship between narrative and seriality, ways in which scientific notations can be used in visual poetry, and aspects of biographical and civil poetry. A finalsection contains a selection of creative approaches to commentary that reflect on research in a manner that is complementary to the critical commentary. The research was carried out through a process of repeated planning and experimentation that has resulted in a variety of forms and procedures, ranging from the accessible and conventional to the idiosyncratic and experimental. A method of investigating narrative was created by allowing narrative and serial formsto intersect throughout the creative work. A means of bringing science and literature into relation was sought through a process of forceful combination of scientific notations with literary or occult materials. And alternative possibilities for biographical poetry were investigated through resistance to celebration and through experiment with formal propertiesin poetry that could be appropriate to Turing. The creative work and critical commentary find new models for the relationship between narrative and seriality in which the will to create narrative is not denied and seriality is not a mere absence of narrative. They find new means by which science and literature can come into contact through visual poetry. They help to define a unique role for poetry in biographical writing in the way that poetry allows the subject to be embodied formally. And they set up a productive dialogue between experimental andmore established writing strategies.

Ce travail de thèse se compose en deux parties :Partie 1Nous nous intéressons à la propagation lumineuse non-linéaire dans des cellules planaires de cristal liquide nématique mélangé avec un colorant, l’effet non-linéaire considéré étant l'effet thermique. Puis, nous nous intéressons à l'amélioration de la fluorescence émise par le colorant.Nous concluons que pour améliorer le spectre de la fluorescence, il faut utiliser une source se propageant en mode soliton, optimiser la distance entre la fibre optique d’excitation de celle de collecte et l’ajout des nanoparticules d'or au cristal liquide. Cette amélioration de la fluorescence ouvrira la voie à la création du laser à colorant assisté par propagation de soliton.Partie 2Nous étudions la dynamique spatiotemporelle d'une cavité en anneau remplie d'un milieu de type Kerr non-instantané et pompée par un faisceau cohérent. Nous effectuons d’abord une étude analytique afin de déterminer les types d’instabilités possibles et leurs seuils. Puis, une étude numérique est menée pour observer l’évolution du champ dans la cavité. Nous montrons l’existence des structures périodiques et localisées. / The work of this thesis consists of two parts:Part 1We are interested in non-linear light propagation in planar cells of nematic liquid crystal mixed with a dye. The non-linear effect is considered to be a thermal effect. Then, we are interested in improving the fluorescence emitted by the dye.We conclude that to improve the fluorescence spectrum, we need to use a source propagating in soliton mode, to optimize the distance between the excitation optical fiber and the collecting one and to add the gold nanoparticles to the liquid crystal. This improvement of fluorescence spectrum will pave the way for the creation of a dye laser assisted with soliton propagation.Part 2We study the spatiotemporal dynamics of a ring cavity filled with a non-instantaneous Kerr-type medium and pumped by a coherent beam. We first carried out an analytical study to determine the types of instabilities and their thresholds. Then, a numerical study is carried out to observe the evolution of the field in the cavity. We show the existence of periodic and localized structures.

Sabendo que os sistemas digitais modernos têm evoluído rapidamente nas últimas décadas e que tal fato levou á sistemas mais rápidos, com grande capacidade de memória, e cada vez menores e mais leves, um dos maiores problemas enfrentados neste processo de evolução é a busca por projetos que consumam baixa potência. Este trabalho apresenta o resultado de um estudo que visa reduzir a potência dissipada em sistemas digitais, aplicando para isso a técnica do Particionamento da Máquina de Estado Finito. Para tanto, utiliza-se de um software desenvolvido especificamente para este fim e que utiliza o cálculo da probabilidade de transição de estados, associado ao emprego de um algoritmo de busca de solução com base no algoritmo Genético. Resultados mostram que, através da utilização da ferramenta apresentada, e dependendo do número de partições realizadas, consegue-se uma redução de consumo de potência na ordem de 50% para algumas Máquinas de Estado Finito, sendo que em alguns casos este valor pode ser superado, demonstrando assim sua eficácia no projeto de sistemas digitais.