Teoria de la computaciòn

ALUMNO:
ABEL
RODRIGUEZ
AMBROSIO
CATEDRATICO:
YESENIA PEREZ REYES

ENSAYOS Y MAPAS MENTALES U_5 Y 6
ISC 4* “B”
“ESTAS SON LAS ULTIMAS COSAS DESAPARECEN UNA A UNA Y NO VUELVEN JAMAS”
UNIDAD 5.-DECIBILIDAD
5.1.- LENGUAJES DECIDIBLES
Dentro de lo referente al tema de LENGUEJES DECIDIBLES, de lamateria de teoría de la computación, analizaremos a los problemas, como un conjunto de frases finitas, es decir que lleguen a un final previamente estructurado, una de las características de los lenguajes decidibles es que deben dar respuesta con un “SI” o un “NO”, cabe mencionar que para que los problemas de este tipo se formalicen, deben decidir si determinada frase pertenece al lenguaje formal,una ves decidido que la frase de entrada pertenece al lenguaje, se dice que es decidible, de otro modo indecidible, se denomina parcialmente decidible cuando una frase perteneciente a un lenguaje aparece de optima manera, pero si no esta en el lenguaje corre indefinidamente, dentro de la materia de teoría de la computación, nos hemos ido dando cuenta que existen maquinas que estudian si loslenguajes son decidibles o no, también se dice que un lenguaje decidible es aquel para el cual existe una MTcapaz de reconocer cualquier cadena dado. Una MT reconoce y acepta cadenas, cuando un lenguaje es semidecidido se llama recursivo numerable y generan gramáticas sin restricciones, estos lenguajes recursivos numerables son bastante generales para los libres de contexto que a su ves son regulares,otra cosa importante son los autómatas de Turing, que son finitos e incapaces de reconocer cadenas de lenguaje decidido, la clave de esto es que estos no terminan eh ahí el principal problema de la automatización, algunas veces lo máximo que se logra es dar instrucciones, a partir de esto nace el concepto de algoritmo implementado a la MT el lenguaje decidible, la base de los lenguajes son lasreglas, axiomas y esquemas que hacen un teorema, esto nos lleva a un conjunto de teoremas que a su ves unidos forman un lenguaje formal, esta se denomina teoría lógica, que se liga a los símbolos en un proceso de automatización, el cual será detectado por la MT, volvemos a decir un computador no siempre lo detecta puesto que este solo lee el algoritmo, es decir ejecuta las instrucciones, definidasen el proceso de teoría lógica y la implementación de los símbolos.
5.2.-EL PROBLEMA DE HALTING.
Es el primer problema indecidible con MT y básicamente consiste en un programa que nos diga si determinado ordenador tiene un fin o no, ejemplificando esto nos podríamos basar en bucles o ciclos infinitos, este tipo de problema también es conocido como de la detención, en este tema Turing también essúper importante, no solo por plantear las bases de las computadoras modernas, sino por deducir que no todos los algoritmos pueden ser solucionados por un computador, la MT también juega un papel importante ya que representa funciones computables y solo da resultados cuando una maquina se detenga, esto quiere decir que solo esperaríamos a que se detenga y ver un resultado, teniendo en cuanta quemucho de lo que maneje en su cinta no tendrá nada que ver con un final que posiblemente se detenga hasta que lo detengamos, en otras palabras no dará un resultado final, después de un análisis de todo esto la gente de la época formula un enunciado que básicamente decía: “una MT tiene una cadena de símbolos que informa si otra MT con un determinado programa y datos iniciales se detendráproporcionando una salida”. Dentro del tema nos daremos cuenta que el objetivo de el problema de Halting es diagnosticarnos cuando un problema de decisión no es decidible, el problema de la parada o la detención en un MT es el mas irresoluble conocido, y no hace mas que detectar si una MT se detendrá con cierta entrada, o entrara en un ciclo infinito, formalmente fue el primer problema que se planteo sin...