Trabajo unidad 3automatas

CURSO DE AUTOMATAS Y LENGUAJES FORMALES
CÓDIGO CURSO 301405_33
ACTIVIDAD Nº 14

VIVIANA YELA CUNDAR
CODIGO: 1126445960
E-mail vivianayela-1987@hotmail.com
CERES VALLE DEL GUAMUEZ-PUTUMAYO

JONTHAN PERILLA CUBILLOS
CODIGO: 1122126973
E-mail sirjonathan4401@hotmail.com
ECBTI – Acacias

ANGELICA M. CONDE
CODIGO 111805617
E-mail angiconde@hotmail.com

EDINSON ALARCONSAAVEDRA.
CÓDIGO: 1117492525
E-mail edisonalarcon@hotmail.com



TRABAJO COLABORATIVO Nº 3

PRESENTADO A:
ING. JAIRO ARMANDO RIAÑO HERRERA
TUTOR

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA (UNAD)
FACULTAD DE CIENCIAS BÁSICAS TECNOLOGIA E INGENIERÍA
2011

INTRODUCCION
La máquina de Turing es un modelo computacional introducido por Alan Turingen el trabajo “ On computable numbers, with an application to the Entscheidungsproblem ”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.
Una máquina deTuring es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. Lamáquina tiene una serie de estados internos finitos que también se pueden numerar en binario.

OBJETIVOS

Objetivo General

Reconocer la importancia y el poder computacional de las Máquinas de Turing en el contexto de la solución de problemas computacionales de reconocimiento de Lenguajes.

Objetivos específicos

Estudiar las Máquinas de Turing y sus propiedades básicas

DESARROLLO TRABAJOCOLABORATIVO Nº 3

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

Alan Mathison Turing nació el 23 de Junio de 1912, en Paddington, Londres. Hasta 1936 todos los mecanismos y autómatas conocidos era de propósito particular, es decir, que todo mecanismo construido o ideado hasta la fecha estaba enfocado en una tarea concreta. Sin embargo, la idea de autómatatal y como es utilizada hoy en día, y que da lugar a la Teoría de autómatas, aparece con la formulación de la Máquina de Turing. Todo parte de la historia ya mencionada sobre lo que se conoció como el segundo problema de Hilbert (Enstscheidungsproblem), que consistía en demostrar que los axiomas de la aritmética ordinaria eran consistentes entre sí (coherentes o sin contradicción). Este problemacondujo a uno más general, el problema de decisión, que pretendía descubrir un método general para determinar si una fórmula de la lógica formal podía o no satisfacerse (declararse verdadera).

Una máquina de Turing es una representación abstracta de un dispositivo de cómputo o informático. Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cintabidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1. El Cómputo empieza con la máquina, en un estado dado, examinando un cuadrado. Borra lo que encuentra allí, imprime un 0 o 1, se mueve a un cuadrado adyacente, y entra en un nuevo estado. Esta conducta es completamente determinada por tres parámetros: (1) el estado en que la máquina está, (2) el número en elcuadrado está examinando, y (3) una tabla de instrucciones. La tabla de instrucciones especifica, para cada estado y entrada binaria, lo que la máquina debe escribir, en qué dirección se debe mover, y en qué estado debe entrar. (Por ejemplo, "Si en Estado 1 examina un 0: imprima 1, se mueve a la izquierda, y entra en Estado 3".) La tabla puede enlistar únicamente estados finitos, cada uno de...