informatica

  Computación:  Máquina de Turing
"... ¿Qué significa esto en lo que se refiere al universo físico? La respuesta de Wheeler a esta pregunta es tan asombrosa como profunda. Concluye que ya no podemos seguir considerando el universo como un hardware que existe "ahí fuera", sino que debemos empezar a verlo como compuesto por un "software 'significativo'" y situado, como dice Wheeler, "quién sabedónde". En otras palabras, hemos empezado a ver el universo como constituido en definitiva no por materia y energía, sino por pura información".  Michael Talbot. "Mas allá de la Teoría Cuántica". Edit. Gedisa 3ª Edición 1995 Barcelona.
§1  Presentación
Encontra de lo que pudiera parecer, la ciencia de la computación y las teorías sobre computabilidad no pertenecen a la disciplina que hoy conocemoscomo "Informática", sino a las matemáticas, que son, con mucho, anteriores a aquella.
A principio del siglo XX, el campo de la matemática teórica estaba en plena efervescencia, gracias sobre todo a los trabajos de Hilbert y Gödel.  En particular Hilbert había planteado ciertas cuestiones que derivaron en las teorías de la computación y la computabilidad, en concreto cual sería el significado dela computabilidad de un procedimiento.
En matemáticas se considera que un método o procedimiento es efectivo para obtener un resultado cuando se cumple que:
El procedimiento puede ser expresado mediante un algoritmo (un número finito de instrucciones concretas  1.2.1);  en el que cada instrucción puede ser expresada por un número finito de símbolos.
El procedimiento puede ser seguido sin errorpara conseguir el resultado en un número finito de pasos.
El procedimiento puede ser (al menos teóricamente) seguido por un humano sin más ayuda que un papel y lápiz.
El procedimiento no exige ninguna habilidad o inteligencia especial por parte de la persona que lo ejecuta.  En lenguaje coloquial diríamos que "hasta un tonto podría hacerlo".  La idea es que solo haya que seguir ciertas reglas deforma mecánica.  Por esta razón cuando se cumplen estas condiciones se dice que el procedimiento es efectivo o "mecánico".

Para dar una definición matemáticamente precisa de lo que es un algoritmo, Turing ideó un dispositivo imaginario al que denominó Máquina de computación lógica LCM ("Logical Computing Machine"), pero que ha recibido en su honor el nombre de máquina de Turing.  Aunque supropuesta es anterior a la aparición de los computadores digitales (1936 "On computable numbers, with an application to the Entscheidungproblem"), actualmente es el objeto central de estudio de los teóricos de la computación.  Precisamente la definición moderna de lo que es "Computable" se basa en este concepto, y del mismo modo que cuando se habla de inteligencia artificial es inevitable referirseal Test de Turing, cuando se habla de algoritmos y computación es casi inevitable encontrar alguna referencia a la máquina de Turing [1].  Por si esto fuera poco, los conceptos subyacentes en la idea han jugado un papel importante en las recientes teorías filosóficas sobre la mente.
Lo que confiere al dispositivo su extraordinaria importancia es que es capaz de resolver cualquier problemamatemático a condición de que haya sido reducido a un algoritmo.
Nota:  Una buena introducción al tema en la Enciclopedia Stanford de Filosofía:  Hodges, Andrew, "Alan Turing"   plato.stanford.edu.

§2  La máquina de Turing
Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia (generalmente uncarácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.  Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia;  recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.
En realidad la máquina de Turing es más una abstracción matemática que un...