Introduccion:
en el tema anterior estudiamos la decibilidad haora nos adentraremos en la investigacion sobre la reducibilidad que ha su vez cobra importacia en la teoria de la computacion, pero antes necesitamos una definicion para poder adentrarnos de lleno en el tema
Reducibilidad:
• Se dice que un problema L1 se reduce en tiempo polinomial determinístico a otro problema L2, si asumiendo que existe un algoritmo A2 en P que resuelve L2 es posible construir un algoritmo A1 en P que resuelva L1.
• Escribiremos L1 W L2 para significar que L1 se reduce a L2.
Intuitiva: Una problema P1 se reduce polinomialmente a otro problema P2, si existe un algoritmo que transforme una instancia del problema P1 en una instancia del problema P2 en tiempo polinomial determinístico.
como podemos apreciar la reducibilidad no es mas que utilisar dos problemas uniendolos para asi poder optimizar polinomialmente el rendimiento de los mismos
Desarrollo:
ya teniendo una idea mas clara a lo que se refiere la reducibilidad podemos adentrarnos en lo que son los problemas insolubles ya que al tener un problema insoluble podremos aplicar la reducibilidad para convertirlo en soluble.
Problemas insolubles
como sera logico para algunos al decir que un problema es insoluble se infiere que es un problema que nuestro automata no puede resolver, veamos unos ejemplos para que esta idea se concrete
ejemplo 1:
De las siguiente imágenes, cual es la más llamativa?
nuestro automata no puede saber cual es la imagen mas llamativa ya que para cada usuario la respuesta puede variar convirtiendo en este problema insoluble.
ejemplo 2:
Un peluquero afeita a todas las personas que no se afeitan a si mismas. El peluquero: ¿se afeita así mismo? (insoluble).
Funciones computables:
Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la tesis Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f.
Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable los matemáticos usaban el término informal efectivamente computable.
Reducibilidad de Turing:
Post propuso un camino para obtener un conjunto no completo para la reductibidad de Turing, definiendo y estudiando reducibilidades intermedias. Así, las diferencias importantes entre la reducción M y la de Turing son obviamente el poder efectuar mas de una pregunta, y en segundo lugar el poder “hacer lo contrario” de lo que indica la respuesta; pero la propiedad realmente relevante resulta ser un poder que cada pregunta dependa esencialmete de las respuestas obtenidas a preguntas anteriores
(“adaptabilidad” de la reducción). Es posible definir reducibilidades intermedias, entre ellas las reducciones por la tabla de variedad, que no son adaptativas.
Y, en efecto, una versión reforzada de los conjuntos simples, los hipersimples, proporciona conjuntos que no son completos respecto de la reductibilidad por tablas de verdad. Post demostró este hecho, y construyo un conjunto hipersimple; nosotros lo tenemos facil por que, de hecho, ya lño tenemos: el propio conjunto SK no solo es simple si no hipersimple.
Asimismo, propuso un concepto de hiper-hipersimple, y demostró que existen, en la esperanza de que no fueran completos respecto reducciones de Turing.
La solucion finalmente requirió un concepto tecnico nuevo, las construcciones por metodos de prioridad, que extendieron otra de las varias contribuciones de Post. Merece la pena comentar que actualmente existen varioas demostraciones diferentes, algunas de las cuales pueden considerarse la culminación del programa estructural de Post; pese a lo cual, los metodos de prioridad han de verse como el camino apropiado de solución.
Bibliografia:
http://www.mitecnologico.com/Main/Reducibilidad
http://cs.uns.edu.ar/~gis/fcc/Archivos/ProblemasInsolubles.pdf
http://asixteco.blogdiario.com/
http://www.mitecnologico.com/Main/ReducibilidadDeTuring
http://eduditec.tecvallarta.edu.mx/tutoriales/index.php?view=article&catid=86%3Ateoria&id=265%3Aunidad6&option=com_content&Itemid=54
www.wordreference.com/definicion/insoluble
Equipo: Los Zork
Teoria De La Computacion Segunda parte:Reducibilidad
Teoria De La Computacion Primera parte:Decibilidad
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.
FUENTES BIBLIOGRÁFICAS:
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.