Maquina De Turing

Tarea Investigación 3- Maquina de Turing con C++

Karen Guzman MG040203 – Kevin Monterrosa MA090347 – Cristofer Muñoz MA090055

mg040203@alumno.udb.edu.sv

ma090347@alumno.udb.edu.sv

ma090055@alumno.udb.edu.sv

RESUMEN - Una de las cosas llamativas de Alan Turing es que sus contribuciones fueron muy variadas, pasando de trabajar en cuestiones de teoría matemática, e incluso de filosofía, a la construcción de cacharros útiles en plena guerra mundial. Es esto último por lo que más se le conoce —por haber pateado nazis—, pero en el mundo de la computación se le recuerda, sobre todo, por una contribución teórica: la máquina que lleva su nombre.

La Máquina de Turing constituye la base de todos los computadores actuales y por eso quizás sea la aportación más valiosa del científico inglés. En realidad la Máquina de Turing fue revolucionaria en dos sentidos: primero, porque fue la primera propuesta de una máquina generalista y flexible cuyas funciones vendrían determinadas por un programa alojado en una memoria abstracta. Y segundo, porque Turing dio una descripción formal y rigurosa de su máquina dentro del marco de la Teoría de Autómatas

MARCO TEORICO

Alan Turing

Alan Mathison Turing, OBE (23 de junio de 1912 en Maida Vale, Londres - 7 de junio de 1954 en Wilmslow, Cheshire) fue un matemático, lógico, científico de la computación, criptógrafo y filósofo británico.

Es considerado uno de los padres de la ciencia de la computación siendo el precursor de la informática moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión de la hoy ampliamente aceptada Tesis de Church-Turing, la cual postula que cualquier modelo computacional existente tiene las mismas capacidades algorítmicas, o un subconjunto, de las que tiene una máquina de Turing. Durante la Segunda Guerra Mundial, trabajó en descifrar los códigos nazis, particularmente los de la máquina Enigma; durante un tiempo fue el director de la sección Naval Enigma del Bletchley Park. Tras la guerra diseñó uno de los primeros computadores electrónicos programables digitales en el Laboratorio Nacional de Física del Reino Unido y poco tiempo después construyó otra de las primeras máquinas en la Universidad de Mánchester. Entre otras muchas cosas, también contribuyó de forma particular e incluso provocativa al enigma de si las máquinas pueden pensar, es decir a la Inteligencia Artificial.

La carrera de Turing terminó súbitamente cuando fue procesado por ser homosexual. No se defendió de los cargos y se le dio a escoger entre la castración química o ir a la cárcel. Eligió lo primero y sufrió importantes consecuencias físicas, entre ellas la impotencia. Dos años después del juicio, en 1954, Turing falleció debido a la ingestión de una manzana contaminada con cianuro en un contexto que indica un posible suicidio

Maquina de Turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.

La máquina de Turing fue descrita por Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society,1 La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.

Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.2 (Turing 1948, p. 61)

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing de hecho capturan la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una precisa definición de un algoritmo o 'procedimiento mecánico'.

Definición de computabilidad efectiva

Una función f (de enteros positivos a enteros positivos) es efectivamente computable si en principio es posible dar una lista de instrucciones completamente definidas y explícitas que determine el valor f(n) para cualquier argumento n.

Definición informal de máquina de Turing

Una máquina de Turing es un tipo específico de máquina idealizada para llevar a cabo computaciones, especialmente computaciones sobre los números enteros positivos expresados en notación monádica (tally notation). La computación se lleva a cabo en una cinta que es infinita en ambas direcciones y que está compuesta por casilleros. Cada casillero está en blanco (el blanco será representado por alguno de los símbolos ´0`, ´S0` o ´B`) o tiene una barra (stroke) escrita en él (la barra será representada por alguno de los símbolos ´1`, ´S1` o ´|`). En todo momento (tanto en el momento inicial como en las computaciones subsiguientes) hay solamente un número finito de casilleros con una barra escrita (los infinitos casilleros restantes están en blanco). En cada etapa de la computación, la máquina (en realidad, el cabezal o la lectora de la máquina) escanea exactamente un casillero de la cinta. La máquina es capaz de borrar una barra en el casillero escaneado, si hay una barra escrita allí, y también

...