• Author / Uploaded
• willi

Citation preview

Universidad De Panamá Facultad De Informática, Electrónica y Comunicación Escuela De Informática Asignación Sumativa #1 Máquinas de Turing Asignatura: Computabilidad y complejidad de algoritmos Profesor: Ayax Mendoza Elaborado por: William Abrego 8-805-929 Fecha: 24/9/2019 1

Máquina de Turing Determinista Definición Formal

Características Las Principales características son:  La entrada que tiene la cinta antes de que comience el cálculo debe consistir en un numero finito de símbolos.  La cinta de la maquina tiene una longitud ilimitada.  El cabezal de lectura y escritura puede ser programable.  La máquina de Turing es capaz de hacer 6 tipos de operaciones fundamentales: leer, 2

escribir, mover hacia la izquierda, mover hacia la derecha, cambiar de estado y detenerse.  Tiene la capacidad de computar cualquier cosa que cualquier computadora moderna pueda calcular.  Está formada por un alfabeto de entrada y uno de salida y por un símbolo especial llamado vacío. Ejemplo Diseñar una Máquina de Turing que sea un contador unario de caracteres del lenguaje con alfabeto Σ = {a,b,c}. Es decir, se deben devolver tantos 1’s como caracteres haya en la palabra de entrada. Considerar la codificación unaria del 0

3

Máquina de Turing No Determinista Definición Formal

Características  Acepta si alguna rama alcanza la configuración aceptadora.  Adivina el Camino correcto y luego comprueba que efectivamente es el correcto.

4

Ejemplo Diseñar una Máquina de Turing que tome como entrada una cadena con M 1’s y N A’s (M