Transwiki:Maquina de turing
De Wikilibros, la colección de libros de texto de contenido libre.
[editar] TURING Y LA TEORIA DE LA MAQUINA
Las máquinas de calcular siempre han obsesionado a la humanidad y desde épocas remotas se pueden encontrar prototipos, o máquinas perfeccionadas en distintas civilizaciones.
En el caso de la cultura occidental, la cultura griega clásica es su referente lejano y, allí, podemos encontrar los prototipos de máquinas de cálculo, junto con los fundamentos de las matemáticas.
Platón es el filósofo más descollante de las matemáticas y sus teorías han sobrevivido hasta el presente y, además, han tenido como adalides a los mejores matemáticos en todas las épocas.
No es pertinente el exponer la teoría de las matemáticas en Platón, pues excede el alcance de esta conferencia. Basta decir que la tesis central de esta filosofía afirma que las entidades matemáticas tienen existencia real y objetiva y, además, pueblan el mundo de la experiencia.
Los precursores de los ordenadores actuales son muchos, pero se pueden mencionar algunos:
Eratóstenes, siglo III a.n.e., quien aparentemente inventa una rueda circular con huecos que funciona con una manivela: de modo que al darle un número dado de vueltas deja obturado un agujero, si el número es compuesto y, lo deja abierto si el número es primo. Además, son famosos sus métodos puramente mecánicos de cribas para determinar números primos menores que un entero dado, o que, satisfagan una cierta propiedad o atributo.
En otras épocas, encontramos a R. Llull, o Lulio,siglo XII, quien intuye un cálculo mecánico para la lógica. Están también, Pascal y su máquina de cálculo con engranajes; G. W. Leibniz como ideólogo de un lenguaje y cálculo universales de la ciencia, la Characterística Universalis; L. Carroll y, además, G. Boole como innovadores de la lógica. En la parte mecánica, también en Inglaterra, está Ch. Babbage, quien a partir de los telares mecánicos se imagina el moderno computador como un motor analítico de cálculo.
En la primera parte del siglo XX, existen muchos intentos de construcción de las máquinas de calcular, entre los que podemos mencionar los de Torres Quevedo, en España, y de Vannevar Bush, en los Estados Unidos.
El científico que nos ocupa lleva a cabo sus investigaciones en los años treinta del siglo XX, las que se dan, no solo con la técnica de la lógica más depurada de su tiempo, sino también dentro de una rigurosa y centenaria tradición matemática que tiene su cúlmen en las universidades alemanas durante siglo XIX y los comienzos del siglo XX.
[editar] ANTECEDENTES HISTORICOS
[editar] EL PROGRAMA DE HILBERT
[editar] EL ENTSCHEIDUNGSPROBLEM, O PROBLEMA DE LA DECISION, Y EL PUNTO DE VISTA DE TURING
[editar] DESCRIPCION DE LA MAQUINA DE TURING
[editar] UNA ABSTRACCION DE LA MAQUINA DE TURING
[editar] EJEMPLOS DE LA MAQUINA DE TURING
Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.
El conjunto de estados es {s1,s2,s3,s4,s5} y el estado inicial es s1. La tabla que describe la función de transición es la siguiente: Estado Símbolo leído Símbolo escrito Mov. Estado sig. s1 1 0 R s2 s2 1 1 R s2 s2 0 0 R s3 s3 0 1 L s4 s3 1 1 R s3 s4 1 1 L s4 s4 0 0 L s5 s5 1 1 L s5 s5 0 1 R s1
El funcionamiento de una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora): Paso Estado Cinta 1 s1 11 2 s2 01 3 s2 010 4 s3 0100 5 s4 0101 6 s5 0101 7 s5 0101 8 s1 1101 9 s2 1001 10 s3 1001 11 s3 10010 12 s4 10011 13 s4 10011 14 s5 10011 15 s1 11011 Parada
La máquina realiza su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa al estado s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su cómputo.
