Teoria De La Computacion Segunda parte:Reducibilidad

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