Alan Turing fue un criptoanalista, matemático e informático
teórico nacido el día 23 de junio de 1912 en Maida Vale un distrito residencial
al oeste de Londres.
Alan Turing es uno de los pioneros en las ciencias de la computación
y por asentar las bases de la informática. También fue el primero en formalizar
el concepto del algoritmo. Además, por todo ello Turing tiene el honor de ser
considerado el padre de la inteligencia artificial esto por pensar y
desarrollar una prueba llamada “Test Turing”, el cual consiste en medir la
capacidad de la máquina para hacerse pasar por un humano.
Alan Turing ayudo a derrotar a los nazis en la segunda
guerra mundial, esto fue posible puesto que pudo descifrar los mensajes
provenientes de la maquina enigma, con esta aportación se dice que sin la ayuda
de Turing la segunda guerra mundial hubiera durado al menos 3 años más.
Su aportación más importante a la informática es conocido
como las máquina de Turing, es un dispositivo teórico que manipula símbolos
sobre una cinta de acuerdo a una tabla de condiciones previamente establecida,
esta aportación se dio en el año 1936, cuando Turing publicó una respuesta al
ensayo del matemático alemán David Hilbert “On Computable Numbers, with an
Application to the Entscheidungsproblem“ donde demostró que algunas de estas
máquinas de Turing serían capaces de realizar cualquier cálculo matemático
concebible si fuera representable con un algoritmo.
En la actualidad se puede decir que nosotros hacemos uso de
una maquina de Turing pues nuestras computadoras hacen uso de un CPU, ya que
este modelo computacional se puede adoptar para simular la lógica de cualquier
algoritmo.
¿Cómo se conformaba la máquina de Turing?
La máquina de Turing, modela de forma matemática una máquina que opera sobre una cinta. En esta cinta hay símbolos que la máquina puede escribir o leer, uno a la vez. Las operaciones que la máquina puede realizar están determinadas por un conjunto finito de instrucciones elementales como “si el estado es 6 y el valor es 0 escribe 1 y pasa al estado 27”.
Una
máquina de Turing consta de las siguientes partes:
- Una cinta que está dividida
en celdas una al lado de la otra. Cada celda contiene un símbolo en algún
alfabeto finito. Dicho alfabeto contiene un símbolo especial en blanco (blank
symbol escrito como ‘B’) y uno o más símbolos adicionales. La cinta se
supone infinita.
- Una cabeza que puede leer y
escribir símbolos en la cinta y mover la cinta a la izquierda o a la
derecha una posición.
- Una tabla de reglas finita
de instrucciones, usualmente tuplas de cinco elementos que dado el estado
(qi) en el que se encuentra actualmente la máquina y el símbolo
(aj) que está siendo leído desde la cinta, indica a la máquina
que realice la siguiente secuencia de acciones:
- Escribe o borra un símbolo
- Mueve la cabeza (a la
izquierda o la derecha)
- Asume el mismo o un nuevo
estado según lo prescrito
- Un registro de estados donde
se guarda el estado de la máquina de Turing.
¿Que es una maquina de Turing?
Teoría de la Maquina de Turing
La maquina de Turing y el Entscheidungsproblem
¿Como diseñar una maquina de Turing con JFLAP?
Ejercicio 1 (EJEMPLO).
- Para este primer ejemplo así queda el diseño.
- Aquí probamos la siguiente entrada: 1000
- Al terminar el paso por paso nos da la siguiente salida: 0111
Por lo tanto podemos concluir que para este primer ejercicio la maquina diseñada trabaja perfectamente y hace lo que nos pide desde un principio.
DESCARGAR EJERCICIOS MT
Información adicional sobre el tema.
- Este es otro simulador de la maquina de Turing, dentro de el link viene su tutorial con varios ejemplos. Y la resolución de ejercicios y ejemplos paso a paso
- Tutorial de JFLAP mas profundo sobre las distintas herramientas que ofrece para la manipulación de maquinas de Turing, viene con imágenes paso a paso de como usar cada una de ellas el ubico inconveniente es que esta en ingles.
No hay comentarios.:
Publicar un comentario