Actividad Laboral Con Maquinas De Turing.docx

Grupo:

CC44

Materia:

Teoría de las Ciencias Computacionales

Tema:

Actividad laboral con las máquinas de Turing

Ciudad:

Guanajuato

Fecha:

26 de noviembre de 2018

Alan Mathison Turing, un matemático, lógico, científico de la computación, criptógrafo, filosofo, maratoniano y corredor de ultradistancia británico nació en Paddington, Londres el 23 de junio de 1912 y falleció en Wilmslow, Cheshire, 7 de junio de 1954.

Un autómata que se mueve sobre una secuencia lineal de datos.

Es: Una máquina que opera mecánicamente sobre una cinta.

Contiene una unidad de memoria finita

Un procesador Finito

Máquina Cuántica; formada por una serie de estados finitos Una cinta

Contiene celdas y se pueden escribir símbolos.

Un cursor Un cabezal

Lee el contenido de una celda o escribe en ella.

Estado llamada Un registro de estado

Almacena el estado de la máquina.

Derivaciones

Estado-1

Contiene las instrucciones del autómata. Posee

Máquina de Turing con Oráculo

Estado-0

Está compuesta por: Lee un carácter en la posición actual.

Símbolo especial actuando como marcador μ Escribe un nuevo símbolo en esta posición. Una tabla de acción No determinista Desplaza el cabezal una celda a la izquierda o a la derecha. Máquina de Turing probabilística Determinista Decide cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual.

Máquina de Turing

Con movimiento stay o "esperar"

Estado inicial Con cinta infinita o ambos lados

Estado Final Con cinta multipista

Representado por: Multicinta

Grafos particulares conformados por: Estados

Versiones

Transiciones Multidimensional

universal

Conjunto finito de estados

Cuántica

Alfabeto de entrada

Libres de contexto Alfabeto de cinta

Reconoce lenguajes: Cuenta con: Regulares

Estado inicial

Estados de aceptación

Transiciones

Bibliografía Hernández Quíroz, F. (Febrero de 2016). http://lya.fciencias.unam.mx/fhq/Cursos/TC/2016-2/tc-mt-modelos-ho.pdf. Obtenido de http://lya.fciencias.unam.mx/fhq/Cursos/TC/2016-2/tc-mt-modelos-ho.pdf Vilca Gutiérrez, C. (2016). Máquinas de Turing y sus aplicaciones. Revista de investigación estudiantil ILUMINATE, 31-39.