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 es capaz es escribir una barra en el casillero escaneado, si el casillero está en blanco. La máquina también es capaz de moverse un casillero a la derecha o un casillero a la izquierda (siempre, uno por vez). La máquina está diseñada de modo tal que en cada etapa de computación se encuentra en un cierto estado qi (que es uno de los estados q1,…,qm) y, además, tiene una lista de m instrucciones que ejecuta la instrucción número i cuando está en el estado qi.

Acciones posibles de una máquina de Turing

(1) Borrar: escribir 0 en lugar de lo que sea que haya en el casillero escaneado.

(2) Escribir: escribir 1 en lugar de lo que sea que haya en el casillero escaneado2.

(3) Moverse un casillero a la derecha.

(4) Moverse un casillero a la izquierda.

(5) Para la computación.

Modos de representar una máquina de Turing

El conjunto de instrucciones correspondiente a una máquina de Turing puede especificarse de tres maneras distintas: por medio de un tabla (machine table), por medio de un flow chart (también flow graph), y por medio de un conjunto de “cuádruplos”.

La definición oficial de función computable por una máquina de Turing

a) los argumentos m1,…,mk de la función serán representados en la notación monádica por bloques de 1s. Cada bloque está separado de los otros por un 0 y, dejando de lado estos bloques la cinta está completamente blanca (i.e. contiene solamente 0s).

(1) (b) Al comienzo, la máquina está escaneando el 1 que está más a la izquierda en la cinta, y estará en el estado número 1.3

(2) (c) Si la función computada le asigna el valor n al argumento representado inicialmente en la cinta, la máquina eventualmente para (halts) con la cinta conteniendo un bloque de n 1s. El resto de la cinta, por supuesto, queda vacío (i.e. contiene solamente 0s).

(3) (d) La máquina para leyendo el 1 que está más a la izquierda en el bloque resultante.

(4) (e) Si la función presuntamente computada no arroja ningún valor para los argumentos que están representados inicialmente en la cinta, la máquina o bien nunca para, o para en alguna configuración no estándar.

Una función numérica de k argumentos (de enteros positivos a enteros positivos) es computable por una máquina de Turing si existe alguna máquina de Turing que la computa en el sentido especificado en (a)-(e).

Funciones no computables

La función diagonal d puede presentarse del modo siguiente:

Teorema: La función d es una función total monódica genuina pero no es computable por una máquina de Turing:

Prueba: Supongamos que d es una de las funciones computables por medio de una máquina de Turing. Dado que el conjunto de las máquinas de Turing es enumerable, a fortiori, el conjunto de las máquinas de Turing

...