The idea of automatic programming using the genetic programming paradigm is a concept that has been explored in the work of Koza and several works since. Most problems attempted using genetic programming are finite in size, meaning that the problem involved evolving a function that operates over a finite domain, or evolving a routine that will only run for a finite amount of time. For problems with a finite domain, the internal representation of each individual is typically a finite automaton that is unable to store an unbounded amount of data. This thesis will address the problem of applying genetic programming to problems that have a ``discrete unbounded domain", meaning the problem involves evolving a function that operates over an unbounded domain with discrete quantities. For problems with an discrete unbounded domain, the range of possible behaviors achievable by the evolved functions increases with more versatile internal memory schemes for each of the individuals. The specific problem that I will address in this thesis is the problem of evolving a real-time deciding program for a fixed language of strings. I will discuss two paradigms that I will use to attempt this problem. Each of the paradigms will allow each individual to store an unbounded amount of data, using an internal memory scheme with at least the capabilities of a Turing tape. As each character of an input string is being processed in real time, the individual will be able to imitate a single step of a Turing machine. While the real-time restriction will certainly limit the languages for which a decider may be evolved, the fact that the evolved deciding programs run in real-time yields possible applications for these paradigms in the discovery of new algorithms. The first paradigm that I will explore will take a naive approach that will ultimately prove to be unsuccessful. The second paradigm that I will explore will take a more careful approach that will have a much greater success, and will provide insight into the design of genetic programming paradigms for problems over a discrete unbounded domain.

The idea of automatic programming using the genetic programming paradigm is a concept that has been explored in the work of Koza and several works since. Most problems attempted using genetic programming are finite in size, meaning that the problem involved evolving a function that operates over a finite domain, or evolving a routine that will only run for a finite amount of time. For problems with a finite domain, the internal representation of each individual is typically a finite automaton that is unable to store an unbounded amount of data. This thesis will address the problem of applying genetic programming to problems that have a ``discrete unbounded domain", meaning the problem involves evolving a function that operates over an unbounded domain with discrete quantities. For problems with an discrete unbounded domain, the range of possible behaviors achievable by the evolved functions increases with more versatile internal memory schemes for each of the individuals. The specific problem that I will address in this thesis is the problem of evolving a real-time deciding program for a fixed language of strings. I will discuss two paradigms that I will use to attempt this problem. Each of the paradigms will allow each individual to store an unbounded amount of data, using an internal memory scheme with at least the capabilities of a Turing tape. As each character of an input string is being processed in real time, the individual will be able to imitate a single step of a Turing machine. While the real-time restriction will certainly limit the languages for which a decider may be evolved, the fact that the evolved deciding programs run in real-time yields possible applications for these paradigms in the discovery of new algorithms. The first paradigm that I will explore will take a naive approach that will ultimately prove to be unsuccessful. The second paradigm that I will explore will take a more careful approach that will have a much greater success, and will provide insight into the design of genetic programming paradigms for problems over a discrete unbounded domain.

Result of this work is a reconstruction of proof, that non-deterministic linear time is strictly more powerful than deterministic linear time. We focus on completeness and clarity either of proof itself, either of all auxiliary propositions, which lead to this result.

No description available.

In this thesis, the theory related to Turing machines and means of their description (with focus on composite diagrams) is presented. The aim of this work is to create an application that allows editing Turing machines described by means of composite diagrams and simulating their computation on specified input configuration (including non-deterministic and multi-tape machines). Furthermore, within the application it will be possible to run the termination analysis of Turing machine in order to determine whether this machine or any of its parts always halt. The resulting application is implemented in Java and the termination analysis is performed using the well-founded orders. And so, one of the results created during this work is a software tool which allows designing and testing of Turing machines described by means of composite diagrams. Resulting application may be used especially during lectures on theoretical computer science, where it can be used to demonstrate computation of some Turing machine.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2017-10-13T14:50:03Z No. of bitstreams: 1 Welton Dias de Lima_.pdf: 1124831 bytes, checksum: 41ffb9304231eacf64174b11566c5ad8 (MD5) / Made available in DSpace on 2017-10-13T14:50:03Z (GMT). No. of bitstreams: 1 Welton Dias de Lima_.pdf: 1124831 bytes, checksum: 41ffb9304231eacf64174b11566c5ad8 (MD5) Previous issue date: 2017-07-12 / Nenhuma / O presente estudo teve o propósito de desenvolver uma revisão bibliográfica em um dos artigos mais importantes e polêmicos no campo da Ciência da Computação, “Computadores e Inteligência” (nome original: Computing Machinery and Intelligence). O texto foi escrito em 1950 por um dos maiores gênios da matemática, que mais tarde revolucionou o mundo, Alan Mathison Turing (1912-1954). A partir de sua percepção crítica, esse excelente trabalho científico contribuiu significativamente para o desenvolvimento do computador digital e também deu início aos primeiros passos para os estudos sobre Inteligência Artificial. A pesquisa teve como objetivos investigar os motivos que levaram Turing a escrever o artigo, destacar as principais contribuições do artigo aos diversos campos do conhecimento, fazer um estudo pormenorizado sobre a pergunta áurea do artigo “Pode uma máquina pensar?” e compreender as principais objeções filosóficas a sua posição. Após análise, constata-se que o artigo escrito por Turing está em dividido em três partes: (i) o jogo da Imitação e o computador digital; (ii) objeções filosóficas à inteligência artificial e, por último, (iii) máquinas que aprendem. Destarte, justifica-se o desenvolvimento da pesquisa na sistematização e compreensão do tema escolhido a partir da Filosofia da Mente. A importância do tema se mostra no interesse significativo da área da filosofia pelos questionamentos realizados, oriundos da área da inteligência artificial. Essas indagações refletem os interesses antagônicos dos pesquisadores em IA. As respostas a essas questões dependem de como é definido "inteligência" ou "consciência" e exatamente que ‘máquinas’ estão sob discussão. Para melhor compreensão do assunto, serão analisados os argumentos de John Turing, John Searle, entre outros pensadores. / The present paper offers a bibliographic review of one of the most important and controversial articles in the field of Computer Science, "Computers and Intelligence" (original title: Computing Machinery and Intelligence). The text was written in 1950 by one of the greatest mathematical geniuses who later revolutionized the world, Alan Mathison Turing (1912-1954). Turing’s excellent scientific work contributed significantly to the development of the digital computer and also gave rise to the first steps in the studies on Artificial Intelligence. The paper investigates the reasons that led Turing to write the article, highlights the main contributions of the article to various fields of knowledge, and provides a critical analysis of Turing’s answer to the question "Can a machine think?". My analysis reveals that Turing’s article can be divided into three parts: (i) the game of Imitation and the digital computer; (ii) philosophical objections and finally (iii) learning machines. Inquiries on these questions justified the development of the research in the uniformization and understanding of key issues in the Philosophy of the Mind. These inquiries reflect the opposing interests of AI researchers, as the answers to these questions depend on how "intelligence" or "consciousness" is defined and what exactly are the "machines" under discussion. For a better understanding of the subject, the arguments of Turing, John Searle, and other thinkers will be used.

Ce travail adopte le cadre de l’ingénierie cognitive en vue de la conception et de l’évaluation d’outils cognitifs dans le domaine de l’administration d’entreprises artisanales. Ce cadre relève d’une approche dite écologique des systèmes de travail. L’objectif général de ce travail est double. D’une part, il s’agit de montrer la pertinence de cette approche écologique eu égard au domaine étudié et d’autre part, de proposer une interface utilisateur pour un système d’aide à la gestion administrative sur support numérique mobile. Plus précisément, nous proposons une modélisation du domaine de travail en considérant certaines de ses caractéristiques les plus complexes à modéliser : la récursivité et la dimension éthique. Ensuite, nous testons une méthode récente pour valider et vérifier cette modélisation (Task Machine Turing Analysis, TMTA). Nous proposons également une nouvelle méthode de validation et vérification d’un domaine de travail, dite méthode des « points de vue ». À partir d’un modèle du domaine de travail de la gestion administrative dans les entreprises artisanales, nous expérimentons plusieurs maquettes d’interfaces pour un système d’aide. Cette expérimentation nous permet de mesurer le degré d’application des principes dirigeant la conception d’interface écologique. Enfin, nous proposons et testons une maquette finale de systèmes à destination des artisans. / This work adopts the cognitive engineering framework for the design and evaluation of cognitive tools interfaces in the administrative handicraft field. This framework relies on an ecological approach of work systems. The objectives of this work were twofold. First, it consisted in showing the heuristic value of the ecological approach. Second, we aimed at proposing a user interface for a mobile digital cognitive tool assisting administrative tasks. More precisely, we proposed to consolidate the work domain analysis framework by considering some of the more complex characteristics to model, that is to say recursion and the ethical dimension. Afterwards, we tested a recent method named “Turing Machine Task Analysis” to validate and verify the work domain model. We also proposed a new verification and validation method for work domain model, named “viewpoints method”. Based on a modeling of the administrative handicraft domain, we tested several user interface mockups for a cognitive tool. This experiment permitted us to measure the degree of application of the Ecological Interface Design principles. Finally, we proposed and tested a final mockup for craftsmen.

This thesis explores the use of artificial neural networks for modelling cognitive processes. It presents an exposition of the neural network paradigm, and evaluates its viability in relation to the classical, symbolic approach in cognitive science. Classical researchers have approached the description of cognition by concentrating mainly on an abstract, algorithmic level of description in which the information processing properties of cognitive processes are emphasised. The approach is founded on seminal ideas about computation, and about algorithmic description emanating, amongst others, from the work of Alan Turing in mathematical logic. In contrast to the classical conception of cognition, neural network approaches are based on a form of neurocomputation in which the parallel distributed processing mechanisms of the brain are highlighted. Although neural networks are generally accepted to be more neurally plausible than their classical counterparts, some classical researchers have argued that these networks are best viewed as implementation models, and that they are therefore not of much relevance to cognitive researchers because information processing models of cognition can be developed independently of considerations about implementation in physical systems. In the thesis I argue that the descriptions of cognitive phenomena deriving from neural network modelling cannot simply be reduced to classical, symbolic theories. The distributed representational mechanisms underlying some neural network models have interesting properties such as similarity-based representation, content-based retrieval, and coarse coding which do not have straightforward equivalents in classical systems. Moreover, by placing emphasis on how cognitive processes are carried out by brain-like mechanisms, neural network research has not only yielded a new metaphor for conceptualising cognition, but also a new methodology for studying cognitive phenomena. Neural network simulations can be lesioned to study the effect of such damage on the behaviour of the system, and these systems can be used to study the adaptive mechanisms underlying learning processes. For these reasons, neural network modelling is best viewed as a significant theoretical orientation in the cognitive sciences, instead of just an implementational endeavour. / Psychology / D. Litt. et Phil. (Psychology)

This thesis explores the use of artificial neural networks for modelling cognitive processes. It presents an exposition of the neural network paradigm, and evaluates its viability in relation to the classical, symbolic approach in cognitive science. Classical researchers have approached the description of cognition by concentrating mainly on an abstract, algorithmic level of description in which the information processing properties of cognitive processes are emphasised. The approach is founded on seminal ideas about computation, and about algorithmic description emanating, amongst others, from the work of Alan Turing in mathematical logic. In contrast to the classical conception of cognition, neural network approaches are based on a form of neurocomputation in which the parallel distributed processing mechanisms of the brain are highlighted. Although neural networks are generally accepted to be more neurally plausible than their classical counterparts, some classical researchers have argued that these networks are best viewed as implementation models, and that they are therefore not of much relevance to cognitive researchers because information processing models of cognition can be developed independently of considerations about implementation in physical systems. In the thesis I argue that the descriptions of cognitive phenomena deriving from neural network modelling cannot simply be reduced to classical, symbolic theories. The distributed representational mechanisms underlying some neural network models have interesting properties such as similarity-based representation, content-based retrieval, and coarse coding which do not have straightforward equivalents in classical systems. Moreover, by placing emphasis on how cognitive processes are carried out by brain-like mechanisms, neural network research has not only yielded a new metaphor for conceptualising cognition, but also a new methodology for studying cognitive phenomena. Neural network simulations can be lesioned to study the effect of such damage on the behaviour of the system, and these systems can be used to study the adaptive mechanisms underlying learning processes. For these reasons, neural network modelling is best viewed as a significant theoretical orientation in the cognitive sciences, instead of just an implementational endeavour. / Psychology / D. Litt. et Phil. (Psychology)

This work includes brief overview of the theory behind two-dimentional languages which was the main theme examined in previous work. Based upon this theory there are next chapters introducing a new concept of three-dimentional and multi-dimentional languages. For each type of language there is a definition of corresponding type of strings and string operations. Finally, for each type of language there are definitions of developed formal gramatics and automata. Along with theory, in work there is an demonstration of developed program, which provides simulation of introduced multidimensional automata.