Ir al documento de Padilla Ezquivel
Ahora suponiendo que ya se sobreentienden un gran número de los conceptos que se tratarán y que la mente de nosotros ya está avierta a una buena interpretación... A continuación... les precento el desarrollo de nuestro tema....
INTRODUCCIÓN:
Como parte de la Carrera de Ingeniería en Sistemas Computacionales, estudiamos lo que es Decibilidad ya que se utiliza en la Teoría de Autómatas y Lenguajes Formales, todo esto dentro de lo que llamamos Teoría de la Computación. Por ello desarrollaremos este ensayo como una opción para que otros estudiantes puedan tener información de este tema.
Vamos a Definir que es la Decibilidad, sus áreas y formas de aplicación, para poder darnos una mejor idea de su utilidad. (Falta definir mejor).
Aunque para poder entender este tipo de textos se deben de tener ciertos conocimientos previos, como saber que es y cómo funciona una Maquina de Turing, y también conocimientos propios del lenguaje técnico de Teoría de la Computación.
DESARROLLO:
En este Ensayo citaremos algunas definiciones de Decibilidad para una mayor comprensión de este texto:
•“En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas. Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema”
•“Se dice que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es”.
•“DECIDIBLE: adj. Log .Mat .Dícese de las proposiciones de un sistema axiomático cuya verdad o falsedad puede demostrarse dentro del sistema”.
Según las Definiciones Anteriores, podemos llegar a concluir que se tiene Decibilidad si podemos encontrar una fórmula, método o algoritmo que nos permita decidir si cierta cadena pertenece a una estructura.
Como ya se había mencionado, la Decibilidad nos sirve en los lenguajes Formales, por lo tanto veremos cuáles son los Lenguajes y su Clasificación:
“Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llama lenguajes recursivos”.
TIPOS LENGUAJES
En vista de que uno de los objetivos de este ensayo es hacer más digerible para el lector este tema, primero daremos una definición general acerca de los lenguajes formales y después una definición más técnica para una mayor comprensión:
“Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que, por ejemplo La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
•las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
•Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
•Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más cortó entre esos dos vértices.
•Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se para en un tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.”
Aquí presentamos una definición más formal:
“Sea M un autómata de Turing: ¿w ∈ L (M)?
Posibles respuestas:
1.M termina en un estado final ⇒ w ∈ L (M)
2.M termina en un estado no final ⇒ w∉L(M)
3.M no termina ⇒ w ∉L (M)
Es un lenguaje RECURSIVO si existe un autómata de TuringM que para ante cualquier entrada y tal que:
•Si w ∈ L ⇒ M termina en un estado final
•Si w∉L ⇒ M termina en un estado no final
L es un LENGUAJE RECURSIVAMENTE NUMERABLE
Si existe un autómata de TuringM tal que:
•Si w ∈ L ⇒ M termina en un estado final
•Si w∉L ⇒ M termina en un estado no final o M no termina”.
“Así, en una primera aproximación, los problemas pueden clasificarse en:
•Computables (o decidibles)
•No computables (o no decidibles)”
Un algoritmo indecidible:
Sea el siguiente algoritmo, debido a Lagarias (1985) :
Por ejemplo, si el valor inicial de X es 7, va tomando los valores:
7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
1 Entrar X
2 Mientras X≠1 hacer:
3 Si X es par, X = X/2
4 Si no, X = 3X +1
5 Parar
Sin embargo, no se puede demostrar que este algoritmo llegue siempre a pararse,
para cualquier número positivo de entrada. Aunque tampoco puede demostrarse lo contrario: que exista algún número para el cual el algoritmo no se para nunca.
El problema de la parada:
Dado un programa (o algoritmo) A y un valor de la entrada X, ¿podemos saber siempre si A se parará o no?
El problema de la parada es no decidible : no hay manera de decir, en general y en un tiempo finito si la ejecución de un programa dado, con una entrada dada, terminará o no.
Además a manera de repaso incluyo 2 videos muy interesantes que encontré que explican de manera adecuada el tema... y algunois de los puntos bases del mismo:
FUENTES BIBLIOGRÁFICAS:
http://entucaramcfly.blogspot.com/2009/06/teoria-de-la-computacion-primera.html
http://grupodecidibilidad.blogspot.com/2007/08/resumen-ejecutivo.html
http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema3.pdf
http://ji.ehu.es/ALF/MHermo/pdfs/los_m%C3%ADos/Tema4.pdf
http://ji.ehu.es/ALF/MHermo/pdfs/los_m%C3%ADos/Tema4.pdf
http://avellano.fis.usal.es/~lalonso/CTS/computacion.pdf
http://es.wikipedia.org/wiki/Decibilidad
http://www.mitecnologico.com/Main/Decibilidad
Diccionario Enciclopédico Quillet. Tomo IV. Página 231.
No hay comentarios:
Publicar un comentario