No description available.

No description available.

Thesis (Ph. D.)--University of Chicago, Dept. of Mathematics, June 2003. / Includes bibliographical references. Also available on the Internet.

Thesis (Ph. D.)--University of Chicago, Dept. of Mathematics, August 1999. / Includes bibliographical references. Also available on the Internet.

No description available.

This thesis develops a formal theory of planning, using a simple paradigm of planning that has been previously explored in work such as GPS, HACKER, STRIPS and NOAH. This thesis analyzes the goal interactions that occur when the goal is stated as a conjunction of sub-goals. In this analysis we assume that the problem has a finite state space, and that operators are reversible. Graph theory can be used to characterize these sub-goal interactions. The entire state space is treated as a graph, and each sub-goal or conjunction of sub-goals defines a subgraph. Each subgraph is composed of one or more connected components. Solving each sub-goal by choosing a connected component that contains a final goal state is a necessary and sufficient condition for solving any planning problem. In the worst case, analyzing goal interactions is shown to be no more effective than enumerating the state space and searching. This complexity proves that no complete algorithm can solve all planning problems in linear time. The technique of goal ordering is analyzed, along with several extensions to that technique. While a generalization of goal ordering is possible, in the worst case generating the goal order requires as much computation as solving the problem by a brute-force search. A technique called capability analysis, derived from the connected component results, uses first-order logic to find the constraints that must apply as sub-goals are achieved. A partial implementation uses counterfactual logic to identify the components of a world state that prevent the remaining sub-goals from being achieved. / M.S.

Thesis (Ph. D.)--University of Chicago, Dept. of Mathematics, June 2000. / Includes bibliographical references. Also available on the Internet.

One method to find the node search number of a graph is to prove identical upper and lower bounds. In four types of grid-like graphs. (h. w)-grids. cylinders. orb webs. and walls, upper bounds are easy to see. However. for tori, the upper bounds are less obvious. requiring two different search strategies. In all cases the lower bounds are not obvious and previously unproven. For these five classes of graphs we develop several techniques for proving lower bounds by taking advantage of the fact that re-contamination does help. We observe that in the five classes of graphs we examine, the node search number can be expressed as a function of the height and width of the graph.

Orientador: Walter Alexandre Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-06T09:39:40Z (GMT). No. of bitstreams: 1 Agudelo_JuanCarlosAgudelo_M.pdf: 2515941 bytes, checksum: 58c117425f8731bb67cf3fc0e1181ad4 (MD5) Previous issue date: 2006 / Resumo: As diferentes interpretações da mecânica quântica levanta sérios problemas filosóficos a respeito da natureza do mundo físico e do estatuto das teorias físicas. Tais interpretações desempenham um papel importante na compreensão dos modelos de computação quântica, e por sua vez os modelos de computação quântica abrem a possibilidade de se confrontar as teses filosóficas que se atrevem a responder a tais problemas. Apesar das relevantes e surpreendentes promessas de uso pragmático e tecnológico da computação quântica, não é por essa vereda que caminha este trabalho: o que aqui se oferece é um novo paradigma de computação (um modelo de computação baseado no paradigma paraconsistente), e se propõe uma nova interpretação da computação quântica através desse novo paradigma, dessa forma colaborando simultaneamente na discussão filosófica a respeito da noção de computabilidade e da mecânica quântica. O presente trabalho introduz a definição do que será chamado de modelo de máquinas de Turing paraconsistentes (MTPs). Tal modelo de computação é uma generalização do modelo clássico de máquinas de Turing. No modelo de máquinas de Turing paraconsistentes, diferentemente do modelo clássico, permite-se a execução de múltiplas instruções de mancha simultânea, dando lugar a multiplicidade de símbolos em diferentes casas da fita, multiplicidade de estados e multiplicidade dc posições da máquina. Considerando que tal multiplicidade de configurações, embora essencial nas MTPs pode ser interpretado como incoerências com respeito às máquinas de Turing clássicas, permite-se acrescentar condições de consistência e inconsistência na execução das instruções nas MTPs. o que servirá então para controlar o estado dc incoerência do sistema. Depois de apresentar o modelo de MTPs, são descritos os modelo de máquinas de Turing quânticas (MTQs) e o modelo dc circuitos quânticos (CQs), ambos introduzidos inicialmente por David Dcutsch. os quais são, respectivamente, generalizações do modelo de máquinas dc Turing clássicas e de circuitos boolcanos clássicos usando as leis da mecânica quântica. Finalmente, estabelecem-se relações entre o modelo de MTPs e os modelos de computação quântica, simulando algoritmos quânticos simples (um CQ que soluciona o chamado problema de Dcutsch e um CQ que soluciona o chamado problema de Deutsch-Josza) e mostrando que o paralelismo quântico, uma característica essencial da computação quântica., pode em alguns casos ser simulado por meio de MTPs. Dessa forma, apesar de o particular modelo de MTPs aqui apresentado ter algumas restrições na simulação de certas características da computação quântica, abre-se a possibilidade de se definir outros modelos de MTPs de maneira a simular tais características. Em resumo, o presente trabalho, na medida cm que oferece um novo paradigma de computação (a saber, a computação paraconsistente) e uma nova interpretação dos modelos de computação quântica (a saber, a interpretação da computação quântica através da computação paraconsistente) contribui para a discussão filosófica a respeito da interpretação dos modelos de computação quântica, e possivelmente da interpretação da própria mecânica quântica. Contudo, não menos importante é o fato de que, apesar de o presente trabalho não pretender se dedicar a questões puramente técnicas da computabilidade, ele de fato abre um imenso campo de investigação a respeito da computação relativizada à lógica e suas implicações - no caso presente, relativizada à lógica paraconsistente / Abstract: The interpretations of quantum mechanics open serious philosophical questions about the nature of the physical world and about the status of physical theories. Such interpretations play an important role in the understanding of models of quantum computing, and models of quantum computing, by their turn, open possibilities to confront and test philosophical theses that dare to address such problems. Although the promising pragmatic and technological applications of quantum computing, this work goes in another way: what is here offered is a new paradigm of computation based upon the pa-raconsistency paradigm, and a new interpretation of quantum computing through this model, in this way simultaneously collaborating in the philosophical discussion about the concepts of computability and of quantum mechanics. This work introduces the definition of what will be called the model of paraconsistent Turing machines (PTMs). Such computational model is a generalization of the classical model of Turing machines. In the PTMs model, differently from the classical Turing machines model, simultaneous execution of multiple instructions is allowed, giving rise to a multiplicity of symbols on different cells of the tape, multiplicity of machine states and multiplicity of machine positions. Such multiplicity of configurations, though essential in the PTMs. can be seen as incoherencies with respect to classical Turing machines: to compensate this, the PTMs permit to operate with consistency and inconsistency conditions to control the global state of incoherence of the system. After introducing the PTMs, the model of quantum Turing machines (QTMs) and the model of quantum circuits (QCs) arc presented. This models arc due to David Dcutsch and arc. respectively, generalizations of the model of classical Turing machines and the model of classical boolean circuits, using the laws of quantum mechanics. Finally, relations between the model of PTMs and models of quantum computing arc established, which permits to simulate simple quantum algorithms (a QC to solve the so called Dcutsch problem and a QC to solve the so called Dcutsch-Jozsa. problem) by PTMs. It is also shown that quantum parallelism, an essential characteristic of quantum computation, may be simulated in some cases by PTMs. Although the particular model of PTMs here presented has some restrictions in the capacity to simulate certain quantum computing characteristics, our work opens the possibility to define other PTM models which could simulate such characteristics. To sum up, the present work, while offering a new paradigm of computation (namely, parconsistent computation) and a new interpretation of quantum computing (namely, interpretation of quantum computation by means of paraconsistent computation) contributes to the philosophical discussion about the interpretation of quantum computation and of the quantum mechanics itself. However, not less important is the fact that, besides its lack of explicit intention towards tccnical questions of computability theory, opens a new line of research about the possibilities of logic-relativized computation and its implications- in the present case, relativized to paraconsistent logics / Mestrado / Logica / Mestre em Filosofia

Submitted by Maike Costa (maiksebas@gmail.com) on 2017-09-20T12:52:54Z No. of bitstreams: 1 arquivototal.pdf: 1155001 bytes, checksum: c813651173e6bf037a98328b32bc7d5a (MD5) / Made available in DSpace on 2017-09-20T12:52:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1155001 bytes, checksum: c813651173e6bf037a98328b32bc7d5a (MD5) Previous issue date: 2016-10-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In the thirties of the last century, several formal versions for the intuitive notion of algorithmic function were offered. Among them, the version of the recursive functions and the version of the Turing-computable functions. Posteriorly, such versions were extended in order to also include the partial algorithmic functions, giving rise, in this way, to the version of the partial recursive functions and to the version of the partially Turing-computable functions. In this context, this research, located into Computability Theory domain and built in the light of theoretical assumptions of Davis (1982), Mendelson (2009), Dias & Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), among others, is intended to rebuild the proof that the given formal versions referred to the intuitive notion of partial algorithmic function, despite being conceptually distinct, they are extensionally equivalents in the sense that they determine the same set of theoretical-numerical functions. As a part of this rebuilding, we shall prove, in na unprecedented way, using quintuples, that every partial recursive function is partially Turing-computable. In the literature, this theorem is proved by means of a set of quadruples. However, defining a lower cardinality set constructed by quintuples, it is possible to prove it in a smaller time interval, which representes a gain from the computational point of view. Besides presenting this alternative proof, posed by the Church-Turing thesis that the set of partial recursive functions includes all the partial algorithmic functions, we shall investigate if this set itself and its infinite subsets are or are not algorithmic. In this survey, we shall demonstrate, in arithmetical terms, with the aid of Rice‟s theorem, that although the set of partial recursive functions is algorithmic, all its subsets which are different from the empty set are not, among which are the set of recursive functions and the set of primitive recursive functions. / Na década de 30 do século passado, foram oferecidas várias versões formais para a noção intuitiva de função algorítmica. Dentre elas, a versão das funções recursivas e a versão das funções Turing-computáveis. Posteriormente, tais versões foram estendidas a fim de abranger também as funções parciais algorítmicas, dando origem, deste modo, à versão das funções parciais recursivas e à versão das funções parcialmente Turing-computáveis. Nesse contexto, esta pesquisa, situada dentro do domínio da Teoria da Computabilidade e construída à luz dos pressupostos teóricos de Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), entre outros, destina-se a reconstruir a prova de que as referidas versões formais dadas para a noção intuitiva de função parcial algorítmica, apesar de conceitualmente distintas, são extensionalmente equivalentes no sentido de que elas determinam o mesmo conjunto de funções numéricas. Como parte desta reconstrução, provaremos, de modo inédito, mediante o uso de quíntuplas, que toda função parcial recursiva é parcialmente Turing-computável. Na literatura especializada, esse teorema é provado por meio de um conjunto de quádruplas. Porém, definindo um conjunto de menor cardinalidade constituído por quíntuplas, é possível prová-lo em um intervalo menor de tempo, o que representa um ganho do ponto de vista computacional. Além de apresentar essa prova alternativa, posto pela Tese de Church-Turing que o conjunto das funções parciais recursivas contém todas as funções parciais algorítmicas, investigaremos se ele próprio e os seus infinitos subconjuntos são ou não algorítmicos. Nesta investigação, demonstraremos, em termos aritméticos, com o auxílio do Teorema de Rice, que embora o conjunto das funções parciais recursivas seja algorítmico, todos os seus subconjuntos diferentes do conjunto vazio não o são, dentre os quais estão o conjunto das funções recursivas e o conjunto das funções recursivas primitivas.