Equivalencia de modelos computacionales

Abstract

Today computer science has taken fundamental importance itself and in another areas of science. In this paper we will review an essential result for “working hypothesis” known as Church-Turing thesis, sentence which states that all computational models have minor or the same power as Turing machine. In first place we overview some basics about sets, alphabets and functions, as well as the definition and another things to keep in mind about Turing Machines. Following this way, we introduce the Church-Turing Thesis. After that, we have a section about another form to represent Turing Machines and we also introduce two models of computation: The Abacus Machine and The Recursive Functions. Next to take advantage of fact that recursive functions are easy for arithmetic, we will show a proof that every recursive function is Turing-computable across the Abacus Machine, with the purpose of have this arithmetic functions in our catalog of Turing-computable functions. On the final we enumerate the Turing machines, prove another lemmas and close this with the fact that a function is Turing-computable if only if is Abacus-computable if only if is recursive.

Hoy en día las ciencias de la computación han tomado una importancia fundamental por si mismas, en otras ramas de las ciencias y en la vida cotidiana. En este trabajo se revisa un resultado que forma parte de los testigos de la Tesis de Church-Turing, enunciado que en síntesis afirma que todo modelo de computación construible tiene menor o el mismo poder de cómputo que una Máquina de Turing. En primer lugar se repasan algunos conceptos básicos sobre conjuntos, alfabetos y funciones, así como la definición y otras cosas a tener en cuenta sobre las Máquinas de Turing. Siguiendo se enunciará la Tesis de Church-Turing haciendo énfasis en algunos aspectos de esta que servirán como preámbulo de los otros 2 modelos computacionales que son tratados. Después seguiremos con una sección sobre una forma de describir Máquinas de Turing más fácil, así como la descripción de la Máquina Abaco y las funciones recursivas. Luego aprovechando de la facilidad de probar que funciones aritméticas son recursivas se revisa que estas funciones pueden ser computadas por Ábacos y Máquinas de Turing. Para finalizar se probó un lema (y algunas otras proposiciones) que nos permiten solo considerar funciones de números naturales y 3 símbolos para las máquinas de Turing lo cual facilita la prueba de que las funciones computables por estos modelos son exactamente las funciones recursivas.