UNIDAD 6 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. Un problema P1 se reduce produce 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 más que utilizar dos problemas uniéndolos para así poder optimizar polinomialmente el rendimiento de los mismos.
Ya teniendo una idea más clara a lo que se refiere a 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.
Estrategia de demostración por reducibilidad
Para demostrar que un problema es insoluble:
1. Suponer que el problema es soluble.
2. Tomar un problema que ya se conozca, o pueda demostrarse, insoluble, para plantear la reducción.
3. Es importante recordar que debe reducirse el problema elegido en el punto 2 al problema que supusimos soluble (demostración por el absurdo)
4. Demostrar la reducción.
No olvidar la conclusión de la demostración.
6.1 Problemas insolubles para la teoría de lenguajes
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. Un problema P1 se reduce produce 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 más que utilizar dos problemas uniéndolos para así poder optimizar polinomialmente el rendimiento de los mismos.
Ya teniendo una idea más clara a lo que se refiere a 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.
Estrategia de demostración por reducibilidad
Para demostrar que un problema es insoluble:
1. Suponer que el problema es soluble.
2. Tomar un problema que ya se conozca, o pueda demostrarse, insoluble, para plantear la reducción.
3. Es importante recordar que debe reducirse el problema elegido en el punto 2 al problema que supusimos soluble (demostración por el absurdo)
4. Demostrar la reducción.
No olvidar la conclusión de la demostración.
6.1 Problemas insolubles para la teoría de lenguajes
Como será lógico para algunos al decir que un problema es insoluble se infiere que es un problema que nuestro autómata no puede resolver.
Se tiene un problema cuando se desea encontrar uno o varios objetos desconocidos que cumplen condiciones y/o relaciones, previamente definidas, respecto a uno o varios objetos conocidos.
TIEMPO POLINOMICO
En computación cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado a partir del número de variables implicadas usando una formula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.
CLASIFICACION DE PROBLEMAS
Los problemas se clasifican por la existencia de una solución en solubles, no solubles e indecidibles.
Un problema se dice soluble si se sabe de antemano que existe una solución para él.
A su vez, los problemas solubles se dividen en dos clases: los algorítmicos y los no algorítmicos.
Un problema se dice algorítmico si existe un algoritmo que permita darle solución.
Un problema se dice no algorítmico si no existe un algoritmo que permita encontrar su solución.
Un problema se dice insoluble si se sabe que no existe una solución para él.
Un problema se dice indecidible si no se sabe si existe o no existe solución para él.
Ejemplo:
Un robot puede apilar en ciertos lugares cajas e diferentes tamaños. La caja a apilar no puede ser más grande que as que ya estén apiladas en dicho lugar. El robot puede solo tomar la caja de más arriba de una pila. ¿Cómo puede el robot pasar las tres cajas apiladas en el lugar A al lugar C usando si es necesario el lugar de apilar B?
6.2 Un Problema Simple Insoluble
1.- Una partícula se mueve en el espacio de manera aleatoria, si en el instante de tiempo t se encuentra en la posición x, ¿Cuál será la posición exacta de dicha partícula 10 segundos después?
Objeto desconocido. Una posición
Objetos conocidos. Posición en el instante de tiempo t.
Condiciones. La partícula se mueve en el espacio de manera aleatoria
Tipo de problema. Insoluble. Debido a que no existe forma de predecir la posición de la partícula, pues se mueve de manera aleatoria.
2.- Problema de la Detención de MT
Un problema de decisión de especial importancia es el “problema de detención de la máquina de Turing” (Halting Problem)
Dada una MT T y una cadena α, ¿existe un algoritmo para decidir si T se detendrá comenzando en el estado inicial con α en la cinta?
Alan Turing, a fines de 1930, enunció y demostró que este problema es insoluble.
Teorema: El problema de la detención de la máquina de Turing no es algorítmicamente soluble.
Resultados auxiliares a utilizar:
Si L es recursivo, entonces su complemento también lo es
Problema de la Detención de MT
Teorema: El problema de la detención de la máquina de Turing no es algorítmicamente soluble.
Resultados auxiliares a utilizar:
Si L es recursivo, entonces su complemento también lo es
Problema de la Detención de MT
Algoritmo Detención MT
Dato de Entrada: T, α
Dato de Salida: Estado
Comienzo
.....
Devolver Estado con valor
“se detiene” o “cicla”
Fin
6.3 FUNCIONES COMPUTABLES
Consisten en las funciones que pueden ser calculadas por una maquina de turing.
Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como máquina de Turing o máquina de registros.
En este apartado, se pueden utilizar los axiomas de Blum para definir una teoría de complejidad computacional sobre el conjunto de las funciones computables. Según la tesis Church-Turing, la clase de las funciones computables es equivalente a la clase de las funciones definidas por funciones recursivas, calculo de λ (lambda), o algoritmos de Markov.
Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una maquinan de turing, una maquina de post, o una maquina de registros.
En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable se conoce como un problema de funciones.
Definen usando como principales operaciones la recursión y composición de funciones forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables.
Una función parcial.
f:⊆ N → N
se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro normalmente se escribe P¹ o P.
una función total
f: N → N
se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro se escribe normalmente R¹ o R .
Una función computable f se llama predicado computable si los valores de la función son booleanos, o sea
f: N → {0,1}
la teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una maquina de turing.
El objetivo es concretar la noción de función calculable, esto quiere decir, una función/expresión cuyos valores se pueden calcular de forma automática a partir de un algoritmo. Surge así una teoría que producirá resultados positivos y negativos.
6.4 Reducibilidad de Turing
En la teoría de la computabilidad, una reducción de Turing de un problema de la A a la B de un problema puede ser entendida como un algoritmo que se podría utilizar para resolver un caso que tenía a su disposición una subrutina para resolver b, pero la definición más formalmente es una reducción Turing es juna función computable por una maquina oráculo con un oráculo para B. reducciones de Turing se puede aplicar tanto a los problemas de decisión y problemas en la función.
Máquina oráculo
Una maquina oráculo es una maquina Turing conectado a un oráculo. El oráculo, en este contexto, se considera como una entidad capaz de responder a alguna colección de preguntas, y por lo general representan como un cierto subconjunto de los números naturales.
Entonces la maquina oráculo puede realizar todas las operaciones habituales de una maquina de Turing, y también puede consultar el oráculo de una respuesta a una pregunta concreta de la forma “es x de A?”.
Una maquina oráculo, como una máquina de turing incluyen:
• Una cinta de trabajo: una secuencia de células sin principio ni fin, cada uno de los cuales puede contener una B (de blanco) o un 1.
• Una cabeza de lectura/escritura: se basa en una sola celda de la cinta de trabajo y puede leer los datos, escribir nuevos datos, y mover hacia la izquierda o la derecha a lo largo de la cinta.
• Un mecanismo de control: que puede estar en uno de un número finito de estados, y que llevara a cabo diferentes acciones (los datos de lectura y escritura de datos, moviendo el mecanismo de control, y el cambio de estados) en función del estado actual y los datos que se leen.
• Una cinta de oráculo: en la que se imprime una secuencia finita de B y 1, correspondiente a la función característica del oráculo conjunto A.
• Una cabeza de oráculo: que como la cabeza de lectura y escritura puede moverse a la izquierda o a la derecha o a lo largo de la cinta de lectura de datos del Oráculo, pero que no puede escribir.
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).
ORACULOS Y PROBLEMAS DE LA PARADA
Es posible postular la existencia de un oráculo que calcula una función no computable, como la respuesta al problema de la parada o algo equivalente. Una maquina con un oráculo de este tipo es una hypercomputadora,
La paradoja de parada todavía se aplica a estas maquinas, es decir, a pesar de que puede determinar si determinadas maquinas de Turing se detienen ante determinadas entradas, no pueden determinar si las maquinas con oráculos de parada equivalentes si se detienen.
Este hecho crea una jerarquía de las maquinas, llamada la jerarquía aritmética, cada uno con un oráculo de parada más potente y un problema aun mas difícil de detener.
Relación de Turing completo a la universalidad computacional.
Como ya se ha definido anteriormente, se corresponde solo parcialmente a la integridad de Turing en el sentido de la universalidad computacional. En concreto, una maquina de Turing es una maquina universal de Turing si y solo si su problema de parada (es decir, el conjunto de insumos para que con el tiempo se detiene) es uno de muchos completa. Por lo tanto, una condición necesaria pero no suficiente para que una maquina sea computacionalmente universal, que es detener el problema de la maquina que Turing completo para el conjunto X recursivamente enumerable de conjuntos.
Bibliografía
Título del libro: Introducción a las Ciencias de la Computación.
Autor: J. Glenn Brookshear.
Cuarta edición.
Título del libro: TEORIA DE LA COMPUTACION, Lenguajes Formales, Autómatas y complejidad.
Autor: J. Glenn Brookshear
Primera edición 1993
“Teoría de la Computabilidad – Transparencias de Clase”. © Dr. Chesñevar, Mg. Cobo, Dr. Martínez - Universidad Nacional del Sur 2002- 2009
http://sistemas.itlp.edu.mx/tutoriales/teoriadelacomputacion/index.htm
Título del libro: Introducción a las Ciencias de la Computación.
Autor: J. Glenn Brookshear.
Cuarta edición.
Título del libro: TEORIA DE LA COMPUTACION, Lenguajes Formales, Autómatas y complejidad.
Autor: J. Glenn Brookshear
Primera edición 1993
“Teoría de la Computabilidad – Transparencias de Clase”. © Dr. Chesñevar, Mg. Cobo, Dr. Martínez - Universidad Nacional del Sur 2002- 2009
http://sistemas.itlp.edu.mx/tutoriales/teoriadelacomputacion/index.htm
