Automatas Y Lenguajes Formales

AUTOMATAS Y LENGUAJES FORMALES

Act 14: Trabajo Colaborativo #. 3

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

ESCUELA DE CIENCIAS BÁSICAS E INGENIERIA

2010

INTRODUCCION

Una máquina de Turing es una máquina idealizada para el procesamiento de información, cuyas acciones están especificadas en términos matemáticos. En definitiva, es un dispositivo que lleva a cabo un procedimiento de cálculo definible en términos finitos. Es un elemento de “matemática abstracta”, y no un objeto físico.

Una máquina de Turing se puede considerar como, abstracta equipo primitivo. Alan Turing quien fue un matemático y criptógrafo británico, inventó la máquina de Turing como una herramienta para el estudio de la compatibilidad de funciones matemáticas.

.

OBJETIVOS

• Analizar la función de las maquinas de Turing y los elementos que la forman.

• Mediante esta técnica se puedan desarrollarse maquinas de Turing complejas a partir de bloque de elementales a partir de maquinas mas pequeñas mediante diagramas de transiciones.

• La construcción de maquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión de los autómatas finitos.

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

Solución

“En 1936, el matemático británico Alan M. Turing mientras era todavía un estudiante, publicó un ensayo titulado On Computable Numbers (Sobre números calculables), con el que contribuyó a la lógica matemática al introducir el concepto teórico de un dispositivo de cálculo que hoy se conoce como la máquina de Turing, importante en el desarrollo de las computadoras digitales modernas.”

Obtenido en: http://es.encarta.msn.com/encnet/error/Error.aspx?mesgid=500-7&url=http%3a%2f%2fes.encarta.msn.com%2fencnet%2frefpages%2fRefArticle.aspx%3frefid%3d761578859

“El concepto de esta máquina, que podría efectuar teóricamente cualquier cálculo matemático, fue importante en el desarrollo de las computadoras digitales. Turing también amplió su trabajo matemático al estudio de la inteligencia artificial y las formas biológicas”.

Obtenido en: http://es.encarta.msn.com/encnet/error/Error.aspx?mesgid=500-7&url=http%3a%2f%2fes.encarta.msn.com%2fencnet%2frefpages%2fRefArticle.aspx%3frefid%3d761578859

2. Describa en qué consiste la prueba de Turing (maquina y persona)

Solución

El matemático Alan Turing propuso un método llamado el test de Turing que permite determinar si un ordenador o computadora se comporta conforme a lo que se entiende como artificialmente inteligente o no, es decir, si las máquinas podrían tener la capacidad de pensar. Cfr http://www.grupometodo.org/maquinas.pdf.

La prueba consiste en que un supuesto juez ubicado en una habitación, una máquina y una persona, ubicado en otras habitaciones. El juez debe descubrir cuál es la persona y cuál es la máquina, permitiéndoles a ambos mentir al responder por escrito las preguntas que el juez les hiciera. El test de Turing tiene como finalidad que si ambos jugadores son lo suficientemente hábiles, el juez no podría diferenciar quién era la persona y quién era la máquina. El límite temporal que Turing puso para que una máquina logre superar el test, es engañando por mucho tiempo a un buen interrogador, y no dejándole aclarar si se está dirigiendo a una persona o a una máquina. Todavía ninguna máquina puede pasar este examen en una experiencia con método científico. Cfr http://www.joseantoniocobena.com/wp-content/uploads/2007/05/INTELIGENCIA%20DIGITAL-LIBRO-EDICI%D3N%20MAYO%202007.pdf

3. ¿Qué es una máquina de Turing y cómo funciona?

Solución

“Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.” Obtenido de: http://www.zator.com/Cpp/E0_1_1.htm

“En realidad la máquina de Turing es más una abstracción matemática que un dispositivo físico o mecánico. El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.” Obtenido de: http://www.zator.com/Cpp/E0_1_1.htm

“Existen diversas "variedades" de una máquina de Turing, pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones:

• Tiene una cinta sobre la que puede desplazarse a izquierda y derecha un cabezal de lectura/escritura. La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito; este conjunto de símbolos se denomina el alfabeto de la máquina. En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #). La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean necesarias para el funcionamiento de la máquina.

• El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.

• Existe un registro de estado que almacena el estado de la máquina. El número de estados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina.

• Existe una tabla de acción, que contiene las instrucciones de lo que hará el autómata. Estas instrucciones representan en cierta forma el "programa" de la máquina. Las ejecución de cada instrucción

...