Máquinas de Turing, decidibilidade e computabilidade

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.