Maquinas de Turing

Definición


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

El problema de la decisión
Dentro del esfuerzo de David Hilbert y
su equipo por formalizar las
matemáticas (para hallar una
formulación de las matemáticas sobre
una base estricta de lógica formal), seplanteó 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?


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.
 ¿Se puede construir un cuadrado,
utilizando regla y compás, queposea un
área igual a la de un círculo dado?
 Se puede construir un cuadrado,
utilizando regla y compás, que posea un
área igual a la de un círculo dado.


Ahora podemos definir cualquier problema
matemático en forma de afirmación:
 Dos y dos suman cuatro es una afirmación
verdadera,
 El área de un cuadrado es el cuadrado de
la longitud de su lado es una afirmación
verdadera
Para cualquier trío de números enteros a,
b y c y cualquier número entero n mayor
que dos se cumple que an+bn=cn es una
afirmación falsa


Implementar un algoritmo














Un algoritmo es un conjunto ordenado de pasos
elementales que nos ayudan a resolver un
problema.
1. ¿Estoy estudiando?
1.1 No → abrir el libro, volver a 1
1.2 Si → pasar a 2
2. ¿Estáencendida la TV?
2.1 No → encenderla, volver a 2
2.2 Si → pasar a 3
3. ¿Quiero realmente estudiar?
3.1 No → cerrar el libro, volver a 2
3.2 Si → apagarla la TV, FIN.

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.
 Definir ahora lo que significa implementar
es fácil:implementar un algoritmo es leerlo
y ejecutarlo
 Una Máquina de Turing es algo
que implementa algoritmos que
representan un problema matemático.


Una Máquina de Turing es un
modelo matemático
Un modelo matemático es un conjunto de
reglas que “encajan” en la explicación y
resolución de un problema, es decir,
que modelan una situación concreta para
poder explicarla y encontrar el modo deresolverla.
 Más aún, se podría decir que un modelo
matemático es un conjunto de reglas
capaces de generalizar y resolver un
problema matemático concreto y cualquier
otro de su misma naturaleza que se pueda
plantear.


Ahora la afirmación una Máquina de
Turing es un modelo matemático cobra
significado: nos dice que es una forma
de resolver cierto tipo de problemas,
que ademásfunciona para cualquier
problema de la misma naturaleza.
 Por lo tanto, uno de los problemas que
será capaz de resolver la Máquina de
Turing es el Problema de la decisión.


Una máquina de Turing es un
autómata
En matemáticas, un autómata es lo que
se conoce como una máquina teórica,
es decir, un dispositivo cuyo
funcionamiento se estudia sin necesidad
de construirlo realmente.
 Enconcreto 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.


Entonces si introducimos una cinta que
conste de dos agujeros y un espacio sin
perforar, que representamos por OOX, el
robot leerá el primer agujero y se
levantará, leerá el segundo y dirá la frase y
al llegar al espacio sin perforar se volverá
a acostar.
Si ahora introducimos una cinta con la
instrucción OXOOOX, el robot se
levantará, se acostará, se volverá a
levantar, dirá dos veces su frase, y
acabará acostado de nuevo.






Esto es básicamente un autómata: un dispositivo
que lee (implementa) unas instrucciones
(algoritmos), y cambia su estado en función de estas
(se sienta, se levanta o dice la frase).
Pero para un...