control de lectura_capitulo 8 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
8.- Introducción a las máquinas de Turing.
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
8.- Introducción a las máquinas de Turing.
Resumen.
La máquina de Turing para desarrollar una teoría acerca de los problemas “indecidibles”, es decir, problemas que ninguna computadora puede resolver.
El problema particular que vamos a abordar es si lo primero que imprime un programa C es Hola, mundo. Aunque podríamos imaginar que la simulación del programa nos permitirá decir qué hace, en realidad tendremos que enfrentarnos a programas que tardan mucho tiempo en producir una respuesta. Este problema (no saber cuándo va a ocurrir algo, si es que alguna vez ocurre) es la causa última de nuestra incapacidad de decir lo que hace un programa.
Este programa es tan transparente que se ha convertido en una práctica habitual presentar los lenguajes mostrando cómo escribir un programa que imprima Hola, mundo en dichos lenguajes.
main()
{
printf("hola, mundo\n");
}
Sin embargo, existen otros programas que también imprimen hola, mundo; a pesar de que lo que hace no es ni mucho menos evidente.
Para entender qué hace este programa, primero observe que exp es una función auxiliar para el cálculo de potencia. El programa principal necesita buscar en los tripletes(x,y,z)en un orden tal que estemos seguros de obtener todos los tripletes de enteros positivos. Para organizar la búsqueda adecuadamente, utilizamos una cuarta variable, total, que se inicia con el valor 3 y, en el bucle while, se incrementa en una unidad en cada pasada, tomando siempre valores enteros finitos. Dentro del bucle while, dividimos total en tres enteros positivos x,y yz, haciendo primero que x varíe entre 1 ytotal-2, y dentro del bucle for, hacemos que y varíe entre 1 y una unidad menos de lo que queda de total después de haberle restado el valor actual de x.Az se le asigna la cantidad restante, que tiene que estar comprendida entre 1 ytotal-2.En el bucle más interno, se comprueba si(x,y,z)cumple la ecuación xn + yn = zn. En caso afirmativo, el programa imprime Hola, mundo y no imprime nada, en caso contrario. Si el valor de n que lee el programa es 2, entonces encontrará combinaciones de enteros tales como total= 12,x=3,y=4yz=5, para las que xn+yn=zn. Por tanto, para la entrada 2, el programa imprime hola, mundo. Sin embargo, para cualquier entero n>2, el programa nunca encontrará tres enteros positivos que satisfagan la ecuación xn+yn=zn, y por tanto no imprimir Hola, mundo. Lo interesante de esto es que hasta hace unos pocos años no se sabía si este programa imprimiría o no el texto Hola, mundo para enteros n grandes.La afirmación de que no lo haría, es decir, que no existen soluciones enteras para la ecuación xn+yn=zn sin>2, fue hecha por Fermat hace 300 años, pero hasta hace muy poco no se ha demostrado. Esta proposición normalmente se conoce como el “último teorema de Fermat”.
La imposibilidad de crear un comprobador de hola mundo se demuestra por reducción al absurdo. Es decir, suponemos que existe un programa, llamado, que toma como entrada un programa P y una entrada I, y establece si P para la entrada imprime Hola, mundo. La Figura 8.3 es una representación de lo que hace H. En concreto, la única salida que proporciona H es o imprimir los caracteres sí o imprimir los caracteres no.Siempre hace una cosa o la otra. Si un problema tiene un algoritmo como H, que siempre establece correctamente si un caso del problema tiene como respuesta “sí” o “no”, entonces se dice que el problema es “decidible”. En caso contrario, el problema es “indecidible”. Nuestro objetivo es demostrar que H no existe; es decir, que el problema de hola-mundo es indecidible.
Bibliografías.
2008 por PEARSON EDUCACIÓN S.A.Ribera del Loira, 2828042 Madrid
Introducción a la teoría de autómatas, lenguajes y computaciónHopcroft, J. E.; Motwani, R.; Ullman, J. D.
Página 1 | 1
Acapulco Gro. 30 de octubre de 2020