automatas


AUTOMATAS Y LENGUAJES FORMALES




ALUMNO:
MYRIAM JANNETH RODRIGUEZ RODRIGUEZ

TUTOR:
JAIRO ARMANDO RIAÑO HERRERA

“TRABAJO COLABORATIVO No. 3”






UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD
ESCUELA DE CIENCIAS BÁSICAS E INGENIERÍA
MAYO 2010





INTRODUCCION


En las presentes unidades se han estudiado lo que se puede considerar las máquinas abstractasque permiten solucionar ciertos tipos de algoritmos, los algoritmos en los que no puede recordarse más que una cantidad fija de información y otros en los que la información desarrollada durante la ejecución del algoritmo puede recuperarse solo en concordancia con la regla “lifo” últimos en entrar primeros en salir, en esta unidad se describe una maquina abstracta, llamada Máquina de turing , quees aceptada de manera amplia como modelo general de computación, aunque las operaciones básicas de esta máquina son comparables en su sencillez a las de las máquinas estudiadas en las unidades anteriores, las nuevas maquinas pueden realizar una amplia variedad de operaciones de computo. Además de aceptar lenguajes les es posible computar funciones y de conformidad con la tesis de Church-Turing,ejecutar casi cualquier
Procedimiento algorítmico concebible
.
En el presente trabajo colaborativo posee una serie de cuestiones teóricas sobre la noción de ‘máquina de Turing’. En cual tratan las tesis centrales sobre comprender y ver como funcionan estas máquinas, así como los conceptos teóricos que aparecen asociados a ellos.

Es así como las tareas típicas se pueden desarrollar en lasmáquinas de Turing, son tareas especialmente útiles para comprender la noción de la computación, y en general para conocer cómo funcionan estas máquinas.

Esperamos que el siguiente trabajo llene las expectativas propuestas por el grupo colaborativo desde el inicio hasta el final de su realización.


OBJETIVOS GENERALES


Reconocer la importancia y el poder computacional de las maquinas deturing en el contexto de la solución de problemas computacionales de reconocimiento de lenguajes.

Estudiar los conceptos fundamentales de la teoría de autómatas y lenguajes formales, para la descripción de ellos.

Conocer la correspondencia entre máquinas, gramáticas y lenguajes, los problemas en los que las teorías tienen aplicación o que han motivado su construcción.

OBJETIVOS ESPECÍFICOSEstudiar las maquinas de turing y sus propiedades básicas
Desarrollar la capacidad de entender los problemas computacionales, y lograr una comprensión total de algunos tópicos de la ciencia de la computación; específicamente en modelos básicos de conmutabilidad y complejidad de problemas.







DESARROLLO DE ACTIVIDADES

1. Realiza una breve síntesis del invento patentado por AlanTuring en 1931.

BIOGRAFÍA 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 deoperaciones matemáticas expresadas en un lenguaje formal determinado. La máquina de Turing era tanto un ejemplo de su teoría de computación como una prueba de que un cierto tipo de máquina computadora podía ser construida.

La Segunda Guerra Mundial ofreció un insospechado marco de aplicación práctica de sus teorías, al surgir la necesidad de descifrar los mensajes codificados que la Marina alemana...