Trabajo Colaborativo Automatas y Lenguajes

AUTÓMATAS Y LENGUAJES FORMALES
TRABAJO COLABORATIVO Nº3

TUTOR:
CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
PROGRAMA DE INGENIERIA DE SISTEMAS
MALAGA – SANTANDER
2011

Introducción

Las maquinas de Turing, son maquinas formales o abstractas es decir sin cables ni componentes físicos y es precisamente de ellas que trataremos en el presente taller.
Laimportancia de dichas maquinas radica en que ellas definen el limite entre los problemas que puede resolver una maquina y los que No, dicho en otros términos marcan el limite entre lo computable y lo no computable; es por ello que es indispensable para nosotros como estudiantes: conocer La Historia, El Funcionamiento, Los Lenguajes Aceptados y todas las demás características inherentes a lasmaquinas de Turing Ya que los principios de funcionamiento de estas se aplican a todas las maquinas automatizadas reales que encontramos hoy en nuestro diario vivir.

Objetivos
* Reconocer la importancia de las maquinas de Turing en la teoría computacional actual.
* Diferenciar los tipos de lenguajes aceptados por una maquina de Turing
* Conocer los tipos de maquinas de Turing existentese identificar sus diferencias

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.
El concepto de "La Maquina De Turing" se conoce también como "La Formula" o "La Ecuación", pero en cierto modo hay posibilidades infinitas de Máquinas de Turing, cada una se corresponde a un "método definido" o aun "algoritmo". Esto se explica sabiendo que como Turing hizo, cada algoritmo en concreto, era escrito como un "set" de instrucciones de una forma estándar. Entonces el trabajo de interpretación y representación mediante un proceso mecánico era posible mediante la introducción de este algoritmo en una Maquina de Turing "singular" llamada La Máquina de Turing Universal. Una Máquina de TuringUniversal hacia posible que otra Máquinas de Turing llevara a cabo los procesos, si le suministraban la descripción de esa Máquina de Turing. Una máquina, para todas las tareas posibles. Es difícil no pensar hoy en día de una Máquina de Turing como en un programa informático, y la tarea de interpretación de este programa como el trabajo que el ordenador.

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

La Prueba De Turing en su aspecto más genérico y aceptado, se basa en que un Juez humano entable una conversación con un ser humano y una máquina (a la vez) e intente establecer cuál es la máquina. Se considera que una máquina podrá superar la Prueba de Turing cuando sea capaz de comportarse tal como un humano y el juez no pueda discernir entre sus interlocutores. Paralograrlo, la máquina debería ser capaz de utilizar un lenguaje natural, razonar, tener conocimientos y aprender. Este conjunto de elementos es, en su mayoría, lo que representa escollos para la inteligencia artificial. A partir de aquí, surgen los detractores de la validez de la prueba de Turing. El argumento principal se basa en que la Prueba sólo evalúa si el sujeto se parece a un ser humano y queeso no implica inteligencia; por un lado existen muchos comportamientos humanos que no se consideran inteligentes (como la susceptibilidad a un insulto o la tentación de mentir) y que una máquina no reproduciría aunque cuente con inteligencia suficiente. Por otro lado, si una máquina fuera capaz de resolver un problema que ningún ser humano puede resolver, fallaría en la Prueba de Turing (serevelaría como no humana) aunque estuviera demostrando una inteligencia superior.

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

Una máquina de Turing es un “dispositivo” como lo eran los autómatas finitos o los autómatas a pila, con más capacidades que éstos. Dispone también de un número finito de estados, uno de ellos inicial, y algunos de ellos finales. Dispone también de una cinta, que...