MAQUINA DE TURING

Aplicaciones

Maquina Oraculo

Generadores de lenguajes

Calculadora de funciones

TIPOS

Maquina de Turing Determinista

Maquina de Turing No Determinista

ESTRUCTURA

Una cinta de longitud infinita dividida en celdas (cada celda puede tener solamente un símbolo tomado de un diccionario de símbolos predefinido).

Un control finito que tiene la capacidad de examinar el algún símbolo de alguna celda y tomar una decisión que depende del símbolo observado y del estado en que se encuentre el control finito. El control es finito porque puede estar solamente en alguno de los estados posibles, habiendo solamente un número finito de ellos.

Un diccionario de símbolos finto.

ALAN TURING

(Alan Mathison Turing; Londres, 1912-Wilmslow, Reino Unido, 1954) Matemático británico. Pasó sus primeros trece años en la India, donde su padre trabajaba en la Administración colonial. De regreso al Reino Unido, estudió en el King's College y, tras su graduación, se trasladó a la Universidad estadounidense de Princeton, donde trabajó con el lógico A. Church. En 1937 publicó un célebre artículo en el que definió una máquina calculadora de capacidad infinita (máquina de Turing) que operaba basándose en una serie de instrucciones lógicas, sentando así las bases del concepto moderno de algoritmo. Así, Turing describió en términos matemáticos precisos cómo un sistema automático con reglas extremadamente simples podía efectuar toda clase de operaciones matemáticas expresadas en un lenguaje formal determinado.

TEORÍA DE LA COMPUTABILIDAD

La Teoría de la Computabilidad consiste en encontrar maneras de representar descripciones de procesos, de tal manera que se pueda asegurar si existe o no una representación. Se dice que un algoritmo es una manera formal y sistemática de representar la descripción de un proceso.

DEFINICIÓN

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á 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.