O estadunidense Edward Fredkin, um pioneiro na área de computação, é conhecido por defender a hipótese do mundo natural ser fundamentalmente um sistema de computação digital se partirmos do princípio de que todas as grandezas físicas são discretas, de modo que cada unidade mínima de espaço e tempo possa assumir apenas uma quantidade finita de estados possíveis. Nesse cenário, as transições de estado do universo nas escalas mais elementares poderiam ser representadas por modelos de autômatos celulares, sistemas computacionais formados de unidades espaciais básicas (células) que modificam seus estados em dependência de uma regra de transição que toma o próprio estado da célula com relação às unidades vizinhas. Quando as mudanças de estados das células são consideradas em escalas maiores, é possível notar um comportamento coletivo que parece seguir uma regra própria, não contemplada na programação básica atuando no nível das células. Fredkin acredita que o nível mais microscópico de nosso universo funcione como um autômato celular e, quando sua computação é tomada em maiores escalas, o padrão coletivo é identificado com os elementos que definimos em nossa física atual como elétrons, moléculas, pedras, pessoas e galáxias, ainda que todos esses elementos macroscópicos sejam apenas o resultado de uma computação alterando estados presentes em unidades mínimas de espaço. Diante disso, a intenção deste trabalho é mostrar que a conjectura de Fredkin pode ser interpretada como uma hipótese reducionista, uma vez que todo sistema explicado por nossas teorias físicas podem ser completamente definidos em termos de uma estrutura computacional. / Edward Fredkin, an American computer pioneer, is known for defending that the natural world be fundamentally a digital computing system, assuming that all physical quantities are discrete, in a way that each unit of space and time can only attain a finite number of possible states. In this scenario, the state transitions of the universe, taking place in the most elementary scales, could be represented by cellular automata models, computer systems formed by basic space units (cells) that modify their states in dependence on a transition rule that takes the state of the cell itself with respect to neighboring units. When cell state changes are considered on larger scales, it is possible to notice a collective behavior that seems to follow a rule of its own, not contemplated in basic programming at the cell level. Fredkin believes that the most microscopic level of our universe works as a cellular automaton and when its computation is taken at larger scales, the collective pattern is identified with the elements we define in our current physics as electrons, molecules, stones, people and galaxies, although all these macroscopic elements are only the result of a computation altering the states in minimum space units. The purpose of this work is to show that Fredkin\'s conjecture can be interpreted as a reductionist hypothesis, since every system explained by our physical theories can be completely defined in terms of a computational structure.

O estadunidense Edward Fredkin, um pioneiro na área de computação, é conhecido por defender a hipótese do mundo natural ser fundamentalmente um sistema de computação digital se partirmos do princípio de que todas as grandezas físicas são discretas, de modo que cada unidade mínima de espaço e tempo possa assumir apenas uma quantidade finita de estados possíveis. Nesse cenário, as transições de estado do universo nas escalas mais elementares poderiam ser representadas por modelos de autômatos celulares, sistemas computacionais formados de unidades espaciais básicas (células) que modificam seus estados em dependência de uma regra de transição que toma o próprio estado da célula com relação às unidades vizinhas. Quando as mudanças de estados das células são consideradas em escalas maiores, é possível notar um comportamento coletivo que parece seguir uma regra própria, não contemplada na programação básica atuando no nível das células. Fredkin acredita que o nível mais microscópico de nosso universo funcione como um autômato celular e, quando sua computação é tomada em maiores escalas, o padrão coletivo é identificado com os elementos que definimos em nossa física atual como elétrons, moléculas, pedras, pessoas e galáxias, ainda que todos esses elementos macroscópicos sejam apenas o resultado de uma computação alterando estados presentes em unidades mínimas de espaço. Diante disso, a intenção deste trabalho é mostrar que a conjectura de Fredkin pode ser interpretada como uma hipótese reducionista, uma vez que todo sistema explicado por nossas teorias físicas podem ser completamente definidos em termos de uma estrutura computacional. / Edward Fredkin, an American computer pioneer, is known for defending that the natural world be fundamentally a digital computing system, assuming that all physical quantities are discrete, in a way that each unit of space and time can only attain a finite number of possible states. In this scenario, the state transitions of the universe, taking place in the most elementary scales, could be represented by cellular automata models, computer systems formed by basic space units (cells) that modify their states in dependence on a transition rule that takes the state of the cell itself with respect to neighboring units. When cell state changes are considered on larger scales, it is possible to notice a collective behavior that seems to follow a rule of its own, not contemplated in basic programming at the cell level. Fredkin believes that the most microscopic level of our universe works as a cellular automaton and when its computation is taken at larger scales, the collective pattern is identified with the elements we define in our current physics as electrons, molecules, stones, people and galaxies, although all these macroscopic elements are only the result of a computation altering the states in minimum space units. The purpose of this work is to show that Fredkin\'s conjecture can be interpreted as a reductionist hypothesis, since every system explained by our physical theories can be completely defined in terms of a computational structure.

No description available.

The reversible logic has the promising applications in emerging computing paradigm such as quantum computing, quantum dot cellular automata, optical computing, etc. In reversible logic gates there is a unique one-to-one mapping between the inputs and outputs. To generate an useful gate function the reversible gates require some constant ancillary inputs called ancilla inputs. Also to maintain the reversibility of the circuits some additional unused outputs are required that are referred as the garbage outputs. The number of ancilla inputs, number of garbage outputs and quantum cost plays an important role in the evaluation of reversible circuits. Thus minimizing these parameters are important for designing an efficient reversible circuit. Barrel shifter is an integral component of many computing systems due to its useful property that it can shift and rotate multiple bits in a single cycle. The main contribution of this thesis is a set of design methodologies for the reversible realization of reversible barrel shifters where the designs are based on the Fredkin gate and the Feynman gate. The Fredkin gate can implement the 2:1 MUX with minimum quantum cost, minimum number of ancilla inputs and minimum number of garbage outputs and the Feynman gate can be used so as to avoid the fanout, as fanout is not allowed in reversible logic. The design methodologies considered in this work targets 1.) Reversible logical right- shifter, 2.) Reversible universal right shifter that supports logical right shift, arithmetic right shift and the right rotate, 3.) Reversible bidirectional logical shifter, 4.) Reversible bidirectional arithmetic and logical shifter, 5) Reversible universal bidirectional shifter that supports bidirectional logical and arithmetic shift and rotate operations. The proposed design methodologies are evaluated in terms of the number of the garbage outputs, the number of ancilla inputs and the quantum cost. The detailed architecture and the design of a (8,3) reversible logical right-shifter and the (8,3) reversible universal right shifter are presented for illustration of the proposed methodologies.

Ce mémoire est composé de deux articles portant respectivement sur les chaînes de spin–1/2 critiques quantiques d’Ising–Kawasaki et de Fredkin. La première chaîne provient d’une chaîne d’Ising classique couplée à un bain thermique par une dynamique de Kawasaki. La deuxième chaîne est une généralisation de la chaîne fortement intriquée de Motzkin. Les deux chaînes sont étudiées avec des conditions frontière périodiques. L’objectif principal est de caractériser la dynamique de ces deux chaînes. D’abord, les exposants critiques dynamiques obtenus suggèrent que, à basse énergie, les deux systèmes comportent de multiples dynamiques. Dans les secteurs à un et deux magnons, nous obtenons un exposant z = 2 pour les deux chaînes. Pour la chaîne d’Ising–Kawasaki, à fort couplage, l’exposant dynamique global est plutôt z = 3. Pour la chaîne de Fredkin, l’exposant dépend de la parité de la longueur de la chaîne. Nous obtenons z = 3.23 ± 0.20 dans le cas pair et z = 2.71 ± 0.09 dans le cas impair. Ensuite, les symétries des systèmes permettent d’obtenir les états propres comme solutions d’ondes de spin dans les secteurs à un et deux magnons. Ces solutions sont présentées pour les deux chaînes et nous étudions leurs continuums de dispersion. Cependant, l’étude de la statistique des niveaux d’énergie indique que de telles solutions ne peuvent être obtenues dans les secteurs de polarisation plus basse. En effet, la distribution des espacements des niveaux d’énergie normalisés dans les secteurs faiblement polarisés correspond à une distribution de Wigner. Selon la conjecture de Berry-Tabor, cela indique que les deux systèmes ne sont pas intégrables. Finalement, pour la chaîne de Fredkin, nous étudions la dispersion des états faiblement excités. Cette dispersion est anomale puisqu’elle dépend de la longueur de la chaîne. En combinant le facteur d’échelle de l’amplitude des branches avec l’exposant dynamique à impulsion fixée, on trouve un exposant dynamique critique z = 2.8. / This thesis is composed of two scientific articles studying respectively the critial quantum spin-1/2 chains of Ising–Kawasaki and Fredkin. The first chain comes from a classical Ising chain coupled to a thermal bath via the Kawasaki dynamic. The second chain is a generalization of the strongly entangled Motzkin chain. The two chains are studied with periodic boundary conditions. The main objective is to characterize the dynamics of these two chains. First, the dynamical critical exponents obtained suggest that, at low energy, the two systems host multiple dynamics. In the one and two magnon sectors, we get an exponent z = 2 for the two chains. For the Ising–Kawasaki chain, at strong coupling, the global dynamical exponent is rather z = 3. For the Fredkin chain, the exponent depends on the parity of the length of the chain. We get z = 3.23 ± 0.20 in the even case and z = 2.71 ± 0.09 in the odd case. Afterwards, the symmetries of the systems make it possible to obtain the eigenstates as spin wave solutions in the one- and two- magnon sectors. These solutions are presented for the two chains and their dispersion continua is studied. However, the study of the statistics of energy levels indicates that such solutions cannot be obtained in lower polarization sectors. Indeed, the distribution of the spacings of the normalized energy levels in the weakly polarized sectors corresponds to a Wigner distribution. According to the Berry-Tabor conjecture, this indicates that the two systems are not integrable. Finally, for the Fredkin chain, we study the dispersion of weakly excited states. This dispersion is anomalous since it depends on the length of the chain. By combining the branch amplitude scaling with the fixed momentum dynamic exponent, we find a dynamical critical exponent z = 2.8.