TP Maquina Turin


Trabajo Práctico: Máquina de Turing.
Matemática discreta y Autómatas.



Profesor: Licenciado Jorge Kamlofsky
Alumnos: Carrizo Cecilia, Tagliazucchi Matías.
Curso: Tercer Año.
Establecimiento: Colegio Leonardo Da Vinci
Año: 2012

Trabajo Práctico: Máquina de Turing
Introducción.
En este Trabajo Práctico detallaremos la Máquina de Turing, su modelo, sus funcionalidades ,técnicas para su construcción y sus modelos. Antes de ello incluiremos un glosario de algunos términos que se encontraran en el desarrollo del Trabajo Práctico y una breve biografía de su creador Alan Turing.
Glosario.

Teoría de autómatas: La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. Lateoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.

Autómatas: Un autómata es un modelo matemático para una máquina de estado finita.

Máquina de estados finitos: Una máquina de estados finitos es una 5-tupla M = (S, I, O, v, w) donde S es el conjunto deestados internos de la máquina M, I y O son los alfabetos de entrada y salida, v: S x I ==> S es la función "Estado siguiente", w: S x I ==> es la "función de salida". 

Autómata de pila: Un  autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa  cadena pertenece al lenguaje que el autómata reconoce.Símbolo: Un dato arbitrario que tiene algún significado a o efecto en la máquina. A estos símbolos también se les llama "letras".

Palabra: Una cadena finita formada por la concatenación de un número de símbolos.

Alfabeto: Conjunto finito de símbolos. Un alfabeto se indica normalmente con , que es el conjunto de letras en un alfabeto

Lenguaje: Un conjunto de palabras, formado por símbolos en unalfabeto dado. Puede ser infinito.

Biografía:

Alan Mathison Turing, OBE (23 de junio de 1912 en Maida Vale, Londres - 7 de junio de 1954 en Wilmslow, Cheshire) fue un matemático, lógico, científico de la computación, criptógrafo y filósofo británico.
Es considerado uno de los padres de la ciencia de la computación siendo el precursor de la informática moderna. Proporcionó una influyenteformalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión de la hoy ampliamente aceptada Tesis de Church-Turing, la cual postula que cualquier modelo computacional existente tiene las mismas capacidades algorítmicas, o un subconjunto, de las que tiene una máquina de Turing. Durante la Segunda Guerra Mundial, trabajó en descifrar los códigos nazis,particularmente los de la máquina Enigma; durante un tiempo fue el director de la sección Naval Enigma del Bletchley Park. Tras la guerra diseñó uno de los primeros computadores electrónicos programables digitales en el Laboratorio Nacional de Física del Reino Unido y poco tiempo después construyó otra de las primeras máquinas en la Universidad de Mánchester. Entre otras muchas cosas, tambiéncontribuyó de forma particular e incluso provocativa al enigma de si las máquinas pueden pensar, es decir a la Inteligencia Artificial.

Máquina de Turing.
Definición:
La  Máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una Máquina de Turing puede ser adaptada para simular la lógica de cualquieralgoritmo  de computador  y es particularmente útil en la explicación de las funciones de un CPU  dentro de un computador.
Modelo de la Maquina de Turing:
Un modelo formal para un procedimiento efectivo deberá poseer ciertas propiedades. Primero, cada procedimiento deberá poder describir de manera finita. Segundo, el procedimiento deberá consistir en paso discretos, cada uno de los cuales puede...