Maq turing

Introducción

Este documento tiene la intención primordial de conocer el concepto y los principios sobre los cuales se fundamenta la máquina de Turing. Durante la investigación realizada se formularon las siguientes interrogantes:
¿Qué es un algoritmo?
¿Podemos demostrar que las máquinas de Turing capturan la noción de algoritmo?
¿Qué es la máquina de Turing?
¿Cuántos estados maneja laMáquina de Turing?
¿Por qué se piensa que la máquina de Turing es una formalización del concepto de algoritmo?
Para ello comenzaremos por conocer algunos conceptos básicos que se trataran a lo largo de este documento.

¿Qué es un algoritmo?
La palabra procede del matemático árabe Al-Khowarizm, quien escribió en el 825 un tratado de aritmética muy conocido durante la Edad Media. No obstante,antes de él ya se conocían ejemplos de algoritmos. Uno de ellos es el popular algoritmo de Euclides que constituye un procedimiento para encontrar el máximo común divisor de dos números. Se trata de dividir entre sí ambos,  formar una nueva pareja con el divisor y el resto y volverlos a dividir. Así, sucesivamente hasta que se consiga un resto cero. El divisor que quede entonces será el máximo comúndivisor de ambos números.  El algoritmo de Euclides supone una regla, unas instrucciones para conseguir un resultado, que se obtendrá siempre sean cuales sean ambos números. Si son muy altos, el procedimiento tendrá más pasos, nada más. De este modo, todas las operaciones aritméticas son algoritmos (sumar, multiplicar, raíces cuadradas, elevar a una potencia…). Todas consisten en realizar unpequeño número de instrucciones que se repetirán cuantas veces sean necesarias para llegar a una conclusión. 
Podemos encontrar muchas definiciones de algoritmo en los textos de programación, todas ellas muy similares.
Descripción exacta, las definiciones más completas o formales:
* Un algoritmo es un conjunto finito de pasos definidos, estructurados en el tiempo y formulados con base a un conjuntofinito de reglas no ambiguas, que proveen un procedimiento para dar la solución o indicar la falta de esta a un problema en un tiempo determinado. [Rodolfo Quispe-Otazu, 2004]
* Secuencia finita de instrucciones, reglas o pasos que describen de forma precisa las operaciones de un ordenador debe realizar para llevar a cabo un tarea en un tiempo más finito. [Donald E. Knuth, 1968]
*Descripción de un esquema de comportamiento expresado mediante un reportorio finito de acciones y de informaciones elementales, identificadas, bien comprendidas y realizables a priori. Este repertorio se denomina léxico [Pierre Scholl, 1988]
En base a lo anterior se puede concluir que un algoritmo es “Una manera formal y sistémica de representar la descripción de un proceso”.
Características:
Lascaracterísticas fundamentales que debe cumplir todo algoritmo son:
* Ser definido: Sin ambigüedad, cada paso del algoritmo debe indicar la acción a realizar sin criterios de interpretación.
* Ser finito: Un número específico y numerable de pasos debe componer al algoritmo, el cual deberá finalizar al completarlos.
* Tener cero o más entradas: Datos son proporcionados a un algoritmo comoinsumo (o estos son generados de alguna forma) para llevar a cabo las operaciones que comprende.
* Tener una o más salidas: Debe siempre devolver un resultado; de nada sirve un algoritmo que hace algo y nunca sabemos que fue. El devolver un resultado no debe ser considerado como únicamente “verlos” en forma impresa o en pantalla, como ocurre con las computadoras. Existen muchos otros mecanismossusceptibles de programación que no cuentan con una salida de resultados de esta forma. Por salida de resultados debe entenderse todo medio o canal por el cual es posible apreciar los efectos de las acciones del algoritmo.
* Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada más ni nada menos que aquello que se requiera para y en su ejecución.
Ya...