dc.creator | Netto, Filipe Ramos | |
dc.date.accessioned | 2024-07-12T18:27:23Z | |
dc.date.available | 2024-07-12T18:27:23Z | |
dc.date.issued | 2024-02-16 | |
dc.identifier.uri | http://repositorio.ufsm.br/handle/1/32291 | |
dc.description.abstract | In this dissertation we look in detail at the mathematical theory of Turing machines,
which serve as a tool for study in the fields of Mathematics and Computing. Alongside
them, we deal with the types of functions that are usually associated with them, as
well as the classifications of languages related to this environment. We take a closer
look at several well-known demonstrations, in which we present a view of them at more
meticulous levels of description. Using examples of problems and situations, we look
at what certain concepts mean and don’t mean. We can check this in our work with
the notion of computability, and its non-extension to certain functions, even if they are
defined in an elementary and direct way. We present some variants of the Turing machines and also the so-called universal machine. We conclude that these variants are
equivalent, as computing models, to the basic version of Turing machines. This allows
us to define the notion of algorithm precisely and independently using these resources. We dealt with various problems by coding their instances, many of them in the
universe of such machines. Using this method, we reach conclusions about the ability
to solve them with the tools in matter, which raise questions, in certain respects, about
the existence of a method that universally solves the same problems. And we also see,
through the definition of mapping reducibility, that from certain unsolvable (or undecidable) problems, by means of the resources considered, we can deduce the inability
to universally find a solution to other problems as well. | eng |
dc.language | por | por |
dc.publisher | Universidade Federal de Santa Maria | por |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 International | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Máquina de Turing | por |
dc.subject | Decidibilidade | por |
dc.subject | Indecidibilidade | por |
dc.subject | Função computável | por |
dc.subject | Turing machine | eng |
dc.subject | Decidability | eng |
dc.subject | Undecidability | eng |
dc.subject | Computability | eng |
dc.title | Máquinas de Turing, decidibilidade e computabilidade | por |
dc.title.alternative | Turing machines, decidability and computability | eng |
dc.type | Dissertação | por |
dc.description.resumo | Nessa dissertação consideramos detalhadamente a teoria matemática das máquinas
de Turing, que servem como ferramenta de estudo em áreas da Matemática e da Computação. Ao lado delas, lidamos com os tipos de funções que lhe são normalmente
associadas, bem como as classificações de linguagens relativas a esse entorno. Trazemos um olhar mais detido a várias demonstrações conhecidas, nas quais expomos
uma visão sua em níveis de descrição mais minuciosos. A partir de exemplares de
problemas e de situações, verificamos o que significam e o que não significam certos conceitos. Podemos checar isto no trabalho com a noção de computabilidade, e
sua não-extensão a certas funções, mesmo que sejam definidas de modo elementar e direto. Apresentamos algumas variantes das máquinas de Turing e também a
chamada máquina universal. E concluímos que tais variantes são equivalentes, como
modelos de computação, à versão básica das máquinas de Turing. Isto nos permite
definir de maneira precisa e independente a noção de algoritmo a partir de tais recursos. Tratamos de diversos problemas a partir de codificações de suas instâncias,
muitos deles no próprio universo de tais máquinas. A partir desse método, chegamos
a conclusões sobre a capacidade de os resolvermos com as ferramentas em questão,
que levantam questões, em certos aspectos, a respeito da existência de um método
que universalmente resolva os mesmos problemas. E ainda vemos, através da definição de redutibilidade por mapeamento, que a partir de determinados problemas
não-solucionáveis (ou indecidíveis), por meio dos recursos considerados, conseguimos deduzir a incapacidade de encontrar universalmente uma solução para também
outros problemas. | por |
dc.contributor.advisor1 | d'Oliveira, Pedro Paiva Zühlke | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/7508611856852819 | por |
dc.contributor.referee1 | Souza, Leonardo Guerini de | |
dc.contributor.referee2 | Sosa, Oscar Francisco Márquez | |
dc.creator.Lattes | http://lattes.cnpq.br/4762012316271051 | por |
dc.publisher.country | Brasil | por |
dc.publisher.department | Matemática | por |
dc.publisher.initials | UFSM | por |
dc.publisher.program | Programa de Pós-Graduação em Matemática | por |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA | por |
dc.publisher.unidade | Centro de Ciências Naturais e Exatas | por |