Touring Ralph

Maquinas 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 conjunto de
reglas capaces de generalizar y resolver un problema
matemático concreto y cualquier otro de su misma
naturaleza que se pueda plantear.
El ejemplo más simple que se me ocurre es, ante el
problema “¿cuántas manzanas tenemos si yo tengo tres y tútienes dos?”, el modelo matemático a aplicar es el que
comprende a los números naturales (1,2,3,4,…) y su suma
finita. Así, cuando nos encontremos con otro caso similar,
como por ejemplo averiguar cuántos años suman las edades
de tres personas, basta con aplicar este modelo para
averiguarlo, es decir, sumar la edad de cada uno de ellos.
Tan fácil como parece.
Ahora la afirmación una Máquina deTuring es un modelo
matemático cobra significado: nos dice que es una forma de
resolver cierto tipo de problemas, que además funciona

1931,
el
matemático
checo
Kurt
Godel
descubrió
que
había
En
teoremas
matemáticos
que eran verdaderos aún
cuando no se pudiesen
probar. Ante esto, Alan
Turing se puso a investigar
aquellos que sí podían ser
probados. Quería intentar
demostrar la vieja idea de
que lasmatemáticas no
son un arte misterioso,
sino una ciencia exacta
regida por reglas lógicas.

Maquinas de Turing (es un modelo
matemático)
La Máquina de Turing (MT) fue introducida por Alan M. Turing
en 1936, y puede considerarse como un modelo abstracto
que formaliza la idea Intuitiva de algoritmo.
MT) Es un modelo computacional que realiza una
lectura/escritura de manera automática sobre unaentrada
llamada cinta, generando una salida en esta misma. Este
modelo está conformado por un alfabeto de entrada y uno
de salida, un símbolo especial llamado blanco (normalmente
b, Δ o 0), un conjunto de estados finitos y un conjunto de
transiciones entre dichos estados.
Su funcionamiento se basa en una función de transición,
que recibe un estado inicial y una cadena de caracteres (la
cinta, la cual esfinita por la izquierda) pertenecientes al
alfabeto de entrada. Luego va leyendo una celda de la
cinta , borrando el símbolo , escribir el nuevo símbolo
perteneciente al alfabeto de salida y finalmente avanza a la
izquierda o a la derecha (solo una celda a la vez), repitiendo
esto según se indique en la función de transición, para
finalmente detenerse en un estado final o de aceptación,representando así la salida.
Esta constituida por los siguiente elementos:
MT = ( E, A, B, e0, F, f)
E = Conjunto de estados, no vacío.
A = Conjunto de símbolos de entrada.
B = Conjunto de símbolos auxiliares.
e0 = Estado inicial.
F = Conjunto de estados finales.

Donde: f: ( E - F ) x
( A È B) x ( I, O, D )

(AÈB)

Þ

Ex

I = movimiento del cabezal a la izquierda.
O = movimiento nulo.
D = movimiento a laderecha.
La máquina de Turing consta de un
cabezal lector/escritor y una cinta infinita
en la que el cabezal lee el contenido,
borra el contenido anterior y escribe un
nuevo valor. Las operaciones que se
pueden realizar en esta máquina se
limitan a:
avanzar el cabezal lector/escritor para la
derecha.
avanzar el cabezal lector/escritor para la
izquierda.
Construcción modular de una MT.
 
Elobjetivo de la creación modular de una
maquina de Turing es poder desarrollar
máquinas complejas a partir de bloques
elementales, a partir de maquinas más
pequeñas,
mediante
diagramas
de
transiciones. La construcción de máquinas
de Turing se lleva a cabo mediante los
diagramas de transición y combinarlos de

La máquina de Touring
•
•

•

•
•

•

•

•

Turing ideó un sorprendente experimento mental....