Psicologia

¿Qué es una Máquina de Turing?
Una Máquina de Turing es un modelo matemático que consiste en un autómata capaz de implementar cualquier problema matemático expresado por medio de un algoritmo. Para poder explicar bien los que es una máquina de Turing y, lo que me interesa más, porqué es tan importante, voy a necesitar que comprendan bien la frase con la que se inicia este artículo.
El problemade la decisión
Dentro del esfuerzo de Hilbert y su equipo por formalizar las matemáticas, se planteó una pregunta para la que no había respuesta: ¿Es posible encontrar una manera sencilla de decidir si un problema matemático cualquiera tiene solución? Cuidado que nos podemos confundir, la pregunta no es si podemos encontrar un método sencillo para descubrir la solución de cualquier problema, sinode decidir (o, si se prefiere, comprobar) si un problema cualquiera puede solucionarse siempre o si existen problemas para los que no puede encontrarse ninguna solución.
Problemas matemáticos
Se podría decir que un problema matemático es una afirmación de una determinada naturaleza que hay que determinar si es cierta o falsa. Veámoslo con un ejemplo.
Implementar un algoritmo
Un algoritmo esun conjunto ordenado de pasos elementales que nos ayudan a resolver un problema. Por ejemplo, si quiero ver el televisor, podría utilizar el siguiente algoritmo para hacerlo:
1. ¿Estoy en el salón?
1.1 No → ir al salón, volver a 1
1.2 Si → pasar a 2
2. ¿Está encendido el televisor?
2.1 No → encenderlo, volver a 2
2.2 Si → pasar a 3
3. ¿Quiero seguir castigando mi cerebro?
3.1 No → apagarlo,FIN
3.2 Si → volver a 2, tú verás lo que haces
Así, un problema matemático expresado por medio de un algoritmo no es más que una afirmación que puede resolverse en un número determinado de pasos elementales. Por ejemplo, dos más dos es cuatro se puede resolver partiendo del dos, sumándole uno, sumándole otro uno y comprobando el resultado. Como éste es cuatro, la afirmación es verdadera.
“UnaMáquina de Turing es un modelo matemático“
“Modelo matemático” es una expresión de esas que se utilizan con cierta frecuencia pero que pocas veces nos paramos a pensar qué significa. Y aunque parezca algo complicado, en realidad se trata de un concepto bastante sencillo.
Un modelo matemático es un conjunto de reglas que “encajan” en la explicación y resolución de un problema, es decir, quemodelizan una situación concreta para poder explicarla y encontrar el modo de resolverla. Más aún, se podría decir que un modelo matemático es un conjuto de reglas capaces de generalizar y resolver un problema matemático concreto y cualquier otro de su misma naturaleza que se pueda plantear.
“Una máquina de Turing es un autómata”
En matemáticas, un autómata es lo que se conoce como una máquinateórica, es decir, un dispositivo cuyo funcionamiento se estudia sin necesidad de construirlo realmente. En concreto un autómata es una máquina teórica que lee unas instrucciones en forma de símbolos y cambia de estado según éstas
Pero, ¿qué es una Máquina de Turing?
Después de esta pequeña introducción en el mundo de la Computación, por fin nos encontramos en disposición de comprender lo que es unaMáquina de Turing y cómo funciona.
Si recopilamos lo que hemos visto hasta ahora, ya sabemos lo que es un modelo matemático, un autómata, un problema matemático, un algoritmo y lo que significa implementar, además de que todo esto debe de tener que ver con el Problema de la decisión, porque por algo se habrá mencionado. Así que sólo nos falta meterlo todo en la coctelera y sacar la Máquina de Turingde ella, así que vamos al lío.
Una máquina de Turing es un autómata que consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda. Por supuesto también  consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba....