2012: año Alan Turing

EL 23 DE JUNIO DE 2012 SE CONMEMORA EL CENTENARIO DEL NACIMIENTO EN LONDRES DE ALAN TURING.

Durante su relativamente breve vida, Turing tuvo un impacto único en la historia de la computación, la informática, la inteligencia artificial, la biología del desarrollo y la teoría matemática de la computabilidad.

En 2012 se celebra el centenario del nacimiento de Alan Turing, con una serie de grandes eventos que tendrán lugar durante todo el año. La mayoría de estos estarán vinculados a los lugares con un significado especial en la vida de Turing, como Cambridge, Manchester y Bletchley Park.

Alan Turing, matemático británico, es considerado el padre de la informática moderna porque en 1936 presentó su máquina universal capaz de ser programada para realizar tareas a distancia.

El trabajo de Alan Turing durante la II Guerra Mundial fue decisivo para la victoria aliada. Coordinó a mas de diez mil profesionales para descrifrar el código secreto de los nazis.

Perseguido por su homosexualidad y enfermo, Alan Turing se suicidó en 1954 a los 41 años.

En 2009 el gobierno británico pidió disculpas públicas por el trato al que se sometió a este insigne matemático y al colectivo gay en general.

Más información: 2012, the Alan Turing Year

La máquina de Turing

Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Este modelo está formado 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 puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final ode aceptación, representando así la salida.

Historia de la Informática. Capítulo 27 – Alan Turing
www.adictosaltrabajo.com

Definición formal

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

M=(Q, \Sigma, \Gamma, s, b, F, \delta),\!

donde:2

  • Q\! es un conjunto finito de estados.
  • \Sigma\! es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
  • \Gamma\! es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (\Sigma \subseteq\Gamma).
  • s \in Q es el estado inicial.
  • b \in \Gamma es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
  • F \subseteq Q es el conjunto de estados finales de aceptación.
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} es una función parcial denominada función de transición, donde L\! es un movimiento a la izquierda y R\! es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S\! como símbolo de “no movimiento” en un paso de cómputo.

Funcionamiento

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 hacia la derecha.
  • Avanzar el cabezal lector/escritor hacia la izquierda.

Visualización de una máquina de Turing, en la que se ve el cabezal y la cinta que se lee.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado, valor) \rightarrow (nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.

La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”.

La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

Más información en Wikipedia: Máquina de Turing.


A %d blogueros les gusta esto: