La Máquina De Turing

La máquina de
Turing
EQUIPO 1
HORA M6

CONTENIDO
Introducción
Definición: Máquina de Turing
Características
Aplicaciones
Ventajas y desventajas

INTRODUCCIÓN
Las máquinas de Turing, así comolos AF y los AP se
utilizan para aceptar cadenas de un lenguaje
definidas sobre un alfabeto A. El modelo básico de
máquina de Turing, tiene un mecanismo de control,
una cinta de entrada que se divideen celdas, y una
cabeza de lectura/escritura que lee un solo símbolo
de la cinta por vez.

DEFINICIÓN: Máquina de Turing
Es un dispositivo de reconocimientos de lenguaje, es
más general que cualquierautómata finito y cualquier
autómata de pila, debido a que ellas pueden reconocer
tanto los lenguajes regulares, como los lenguajes
independientes de contexto y además muchos otros
tipos delenguajes.
 

CARACTERISTICAS
Alberga un número finito de condiciones, a las que llamó configuraciones-m ( ).
La máquina tiene una cinta dividida en celdas, cada una de los cuales puede
tener escrito unsímbolo
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 dichosestados.
Podemos realizar cualquier cálculo que se nos ocurra con una máquina de
Turing.

APORTACIONES
Las máquinas de Turing pueden desempeñar diversas actividades
además de reconocimientos delenguaje. De hecho, las máquinas de
Turing se toman como modelos teóricos de la computadora. Borrar
símbolo de la celda activa (E).
Mover la cinta una posición hacia la izquierda (L).
Mover la cinta unaposición hacia la derecha (R).
Finalmente, en cada paso puede producirse un cambio en la
configuración.

VENTAJAS Y DESVENTAJAS
Ventaja:
Utiliza signos que funcionan en doble sentido
Una de lasventajas de las máquinas de Turing sobre otros modelos es que permite
aceptar lenguajes más generalistas.
Desventaja:
El problema de la parada o detención
Por otra parte las desventajas serían que si...