Maquina de turing

UNIVERSIDAD AUTONÓMA DEL CARMEN
Dependencia Área Ciencias de la Información

PRESENTA:

MARTÍNEZ DOMÍNGUEZ IRIS SARAÍ

ARCOS LOPEZ JOAQUIN ANTONIO

TRABAJO FINAL

MAQUINA DE TURING

SIMULACIÓN

INGENIERÍA EN SISTEMAS COMPUTACIONALES

DR. ERNESTO BAUTISTA THOMPSON

Cd. del Carmen, Campeche a 31 mayo 2010

INDICERESUMEN 3

INTRODUCCION 4

PROBLEMA PLANTEADO 10

DESCRIPCIÓN DEL MODELO DESARROLLADO 11

PRUEBAS 15

RESULTADOS 17

CONCLUSIONES 20

REFERENCIAS 21

RESUMEN

Este proyecto final arrojo como resultado el siguiente reporte sobre las experiencias y resultados que obtuvimos con el modelo de la maquina de Turing. Antes de ir al reporte se explicaran una serie de conceptos queayudarán a comprender con mas facilidad lo de lo que trata este proyecto antes de entrar de lleno al reporte en el cuál se narrarán las experiencias, los problemas y sus soluciones, que se presentaron durante el desarrollo de este proyecto final.

Al comienzo de este semestre no se tenía conocimiento de ningún tipo de compilar o software para realizar simulación, pero durante el paso del tiempo sefueron conociendo una diversidad de elementos y herramientas para desarrollar sistemas modelados, ante esto este proyecto se realizo en base al programa de Netlogo, donde se encuentran una gama de simulaciones ya establecidas, con las cuales se puede empezar a practicar y observar que es lo que se puede lograr con dicho programa.

INTRODUCCION

MÁQUINA DE TURING

INTRODUCCION
La máquina deTuring es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres en 1936, 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áticay que nos diga si esa sentencia es cierta o no. Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.

DESCRIPCIÓN

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal leeel 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.
El cómputo es determinado a partir de una tabla de estados de la forma:
(estado, valor) [pic](nuevo estado, nuevo valor, dirección)
Estatabla 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 ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad dealgoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear unamáquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.
La idea subyacente es el concepto de que una máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo...