Computabilidad y equivalencias al problema de la detención

Abstract

In this project a tool named Turing machine is used for classifying math problems through their complexity, that is, one is harder than other if it has a major complexity degree. The complexity degree of a math problem is measured from its relation with some special sets defining from what’s a Turing machine can do or do not. The Turing machines are the theoric ancestors of the computers, but working with Turing machines give us the advantage of we do not have physics limitations as with the real ones. Firstly, we will develop the theory of Turing machines until we get to the well-known halting problem, after that we give some applications of it. In the applications we study the complexity degree of three important problems: 1. Computers the connected component of a vertex in a computable graph. 2. Compute a maximal ideal in a commutative computable ring. 3. Hilbert's tenth problem. All of these three problems are complexity-equivalents but none of them is solvable.

En este trabajo se utilizará una herramienta matemática conocida como máquina de Turing para clasificar problemas dentro de la misma matemática a partir de su complejidad, es decir, un problema más difícil de resolver que otro tendrá un grado de complejidad mayor. Dicho grado de complejidad de un problema matemático será medido dependiendo de la comparación de dicho problema con ciertos conjuntos definidos a partir de lo que puede y no puede hacer una máquina de Turing. Las máquinas de Turing son el predecesor teórico de las computadoras, y trabajar con máquinas de Turing, al ser objetos teóricos, nos da la ventaja de no tener las limitaciones físicas de las computadoras, tales como el tiempo de cómputo y la cantidad de memoria finita. Se desarrollará primeramente la teoría de las máquinas de Turing y hasta llegar a un problema del conocido como el problema de la detención, del cual se darán varias aplicaciones. Dentro de las aplicaciones se calculará el grado de complejidad de tres problemas matemáticos: 1. calcular la componente conexa de un vértice en un grafo computable. 2. Calcular un ideal maximal dentro de un anillo conmutativo computable. 3. el décimo problema de Hilbert, los cuales resultarán ser equivalentes e complejidad, pero ninguno de ellos soluble.