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.
Ejemplo
• Ordenar se reduce a encontrar el menor
• Sabemos que existe Menor(i; j), que devuelve el elemento menor del segmento del arreglo A[i, j].
Ejemplo
PROCEDIMIENTO Ordena(A; n)
COMIENZA
PARA i =1 A n HAZ
j = Menor(i; n)
intercambia(i; j)
FINPARA
TERMINA
6.2. Problemas Insolubles Teoría de Lenguajes
Ejemplo 1.- Sea el problema Pacept el siguiente problema:
Pacept: ¿Existe un
Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una determinada cadena, α, pertenece al lenguaje que reconoce la máquina de Turing T?
Para demostrar que Pacept no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Pacept implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Pacept. Demostración: Supongamos que Pacept es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), X, que resuelve Pacept. X toma como datos de entrada la descripción de una máquina de Turing T y una cadena α y determina en un tiempo finito si T acepta o no a la cadena α. Es decir X recibe como entrada al par (T,α) y retorna un 1 si T acepta α, mientras que devuelve la salida 0 si T no acepta α.
Construyamos a partir de X, un procedimiento efectivo (o máquina universal de Turing) Y
La máquina Y recibe como entrada un par (T’,α), la cadena de ambos problemas es la misma, lo que necesitamos es un proceso adicional que modifique T’ de manera que las respuestas de X, respondan el problema de la detención. Este proceso adicional se lleva a cabo en la máquina universal ΔX que realiza lo siguiente:
a. Recibe como dato de entrada la máquina de Turing T’.
b. Modifica T’ manteniendo su definición de quíntuplas pero indicando que todos los estados son aceptadores.
c. Retorna la máquina modificada con el nombre T.
Combinando las máquinas X y ΔX, tenemos la máquina universal Y que tiene el siguiente comportamiento:
1. Y recibe como entrada el par (T’, α).
2. La máquina universal Y utiliza ΔX, la cual a partir de T’ construye T.
3. El par (T, α) es ingresado a la máquina universal X.
4. Si la respuesta de X es 1 entonces T acepta α pero entonces T’ se detiene sobre α.
Dado que T se comporta como T’ solo que siempre que se detiene acepta, podemos afirmar que T’ se detiene sobre α y que por lo tanto Y emite un 1
5. Si la respuesta de X es 0 entonces T no acepta α pero entonces T’ no se detiene sobre α. Dado que T tiene a todos sus estados como aceptadores, significa que para no aceptar la cadena, la única posibilidad es que T no se haya detenido. Como T se comporta como T’, podemos afirmar que esta tampoco se detiene y por lo tanto Y emite un 0, ya que T’ no se detiene sobre α.
Conclusión:
• La máquina universal Y retorna 1 (T’ se detiene sobre α) si X retorna 1 (T acepta α).
• La máquina universal Y retorna 0 (T’ no se detiene sobre α) si X retorna 0 (T no acepta α).
Hemos mostrado como construir la máquina universal Y que resuelve el problema de la detención a partir de la máquina universal X que resuelve un problema que supusimos soluble.
Sabemos por hipótesis que el problema de la detención es un problema insoluble, por lo tanto la solución encontrada mediante la máquina universal Y no puede existir. Lo que implica que alguna de sus componentes no puede existir, es decir o bien X, o bien ΔX no existe. Como por construcción ΔX existe, luego X no. Podemos entonces concluir que Pacept es un problema no-soluble.
Ejemplo 2.- Sea el problema Palguna el siguiente problema:
Pacept: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing se detiene sobre alguna cadena? Para demostrar que Palguna no es soluble, comenzaremos suponiendo que lo es, llegando de esta manera a un absurdo. Este absurdo tendrá lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet. Expresado de otra manera, demostramos que Pdet se reduce a Palguna. Demostración: Supongamos que Palguna es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), Alguna, que resuelve Palguna. Alguna toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T se detiene sobre alguna cadena o no. Es decir Alguna recibe como entrada (T) y retorna un 1 si T se detiene para alguna cadena, mientras que devuelve la salida 0 si T no se detiene para ninguna cadena.
Construyamos a partir de Alguna, un procedimiento efectivo (o máquina universal de Turing) Detención
La máquina Detención recibe como entrada un par (T’,α), el problema Palguna solo tiene como entrada una máquina de Turing, por lo que necesitamos un proceso adicional que combine T’ y α de manera que las respuestas de Alguna, respondan el problema de la detención. Este proceso adicional se lleva a cabo en la máquina universal ΔX que realiza lo siguiente: a. Recibe como dato de entrada la máquina de Turing T’ y la cadena α. b. Construye una máquina de Turing T tal que: i. Para la cadena α se comporta como la máquina de Turing T’. j. Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla indefinidamente. Combinando las máquinas universales Alguna y ΔX, tenemos la máquina universal Detención que tiene el siguiente comportamiento: 1. Detención recibe como entrada el par (T’, α). 2. La máquina universal Detención utiliza ΔX, la cual a partir de T’ y α construye la nueva máquina de Turing T. 3. La máquina de Turing T obtenida en el paso anterior es ingresada a la máquina universal Alguna. 4. Si la respuesta de Alguna es 1 entonces T se detiene para alguna cadena. De la manera en la que construimos T esa cadena necesariamente es la cadena α (ya que para el resto sabemos que la máquina siempre cicla) como el comportamiento de T frente a la cadena α es el mismo que tiene la máquina T’ entonces podemos afirmar que T’ se detiene sobre α y que por lo tanto Detención emite un 1 5. Si la respuesta de Alguna es 0 entonces T no se detiene para ninguna cadena. De la manera en la que construimos T la única cadena sobre la que T podía detenerse era α y que el comportamiento frente a esta cadena era el mismo que el de la máquina T’. Podemos entonces afirmar, que la máquina de Turing T’ tampoco se detiene frente a la cadena y que por lo tanto la respuesta que emite Detención es igual a 0. Conclusión: • La máquina universal Detención retorna 1 (T’ se detiene sobre α) si Alguna retorna 1 (T se detiene sobre alguna cadena). • La máquina universal Detención retorna 0 (T’ no se detiene sobre α) si Alguna retorna 0 (T se detiene sobre ninguna cadena). Hemos mostrado como construir la máquina universal Detención que resuelve el problema de la detención a partir de la máquina universal Alguna que resuelve un problema que supusimos soluble. Sabemos por hipótesis que el problema de la detención es un problema insoluble, por lo tanto la solución encontrada mediante la máquina universal Detención no puede existir. Lo que implica que alguna de sus componentes no puede existir, es decir o bien Alguna, o bien ΔX no existe. Como por construcción ΔX existe, luego Alguna no puede existir. Podemos entonces concluir que Palguna es un problema no-soluble. Ejemplo 3.- Sea el problema Pvacio el siguiente problema: Pvacio: ¿Existe un procedimiento efectivo capaz de determinar si una máquina de Turing no acepta ninguna cadena? En este caso tomaremos como el problema insoluble a reducir a este al problema de la aceptación Pacept, demostrado como insoluble anteriormente. Demostración: Supongamos que Pvacio es un problema de decisión soluble. Al ser un problema soluble, entonces existe un procedimiento efectivo (o máquina universal de Turing), Sol Vacio?, que resuelve Pvacio. Sol Vacio toma como datos de entrada la descripción de una máquina de Turing T y determina en un tiempo finito si T no acepta cadena alguna. Es decir Sol Vacio recibe como entrada T y retorna un 1 si T no acepta cadena alguna, mientras que devuelve la salida 0 si T acepta alguna cadena.
Construyamos a partir de Sol Vacio, un procedimiento efectivo (o máquina universal de Turing) Aceptación
La máquina Aceptación recibe como entrada un par (T’,α), el problema Pvacio solo tiene como entrada una máquina de Turing, por lo que necesitamos un proceso adicional que combine T’ y α de manera que las respuestas de Sol Vacio, respondan el problema de la aceptación. Este proceso adicional se lleva a cabo en la máquina universal ΔX que realiza lo siguiente: a. Recibe como dato de entrada la máquina de Turing T’ y la cadena α. b. Construye una máquina de Turing T tal que: i. Para la cadena α se comporta como la máquina de Turing T’. j. Para toda cadena que no sea α la nueva máquina T nunca se detiene o cicla indefinidamente. Combinando la máquinas universales Sol Vacio y ΔX, tenemos la máquina universal Aceptación que tiene el siguiente comportamiento: 1. Aceptación recibe como entrada el par (T’, α). 2. La máquina universal Aceptación utiliza ΔX, la cual a partir de T’ y α construye la nueva máquina de Turing T. 3. La máquina de Turing T obtenida en el paso anterior es ingresada a la máquina universal Sol Vacio. 4. Si la respuesta de Sol Vacio es 1 entonces T no acepta cadena alguna. De la manera en la que construimos T la única cadena sobre la que había incertidumbre con respecto a la aceptación o no es α (ya que para el resto sabemos que la máquina siempre cicla). Como el comportamiento de T frente a la cadena α es el mismo que tiene la máquina T’ entonces podemos afirmar que T’ no acepta la cadena α ya que de lo contrario habría una cadena que T aceptaría. Por lo tanto Aceptación debe emitir un 0 5. Si la respuesta de Sol Vacio es 0 entonces T acepta alguna cadena. De la manera en la que construimos T la única cadena que pudo ser aceptada es α. Como la aceptación de α depende de T’ (debido a la manera en que T fue construida) podemos asegurar que T’ acepta α y por lo tanto la máquina universal Aceptación retorna el valor 1. Conclusión: • La máquina universal Aceptación retorna 1 (T’ acepta α) si Sol Vacio retorna 0 (T acepta alguna cadena). • La máquina universal Aceptación retorna 0 (T’ no acepta α) si Sol Vacio retorna 1 (T no acepta cadena alguna). Hemos mostrado como construir la máquina universal Aceptación que resuelve el problema de la aceptación (Pacept) a partir de la máquina universal Sol Vacio que resuelve un problema Pvacio. Sabemos por hipótesis que el problema de la aceptación es un problema insoluble, por lo tanto la solución encontrada mediante la máquina universal Aceptación no puede existir. Lo que implica que alguna de sus componentes no puede existir, es decir o bien Sol Vacio, o bien ΔX no existe. Como por construcción ΔX existe, luego Sol Vacio no puede existir y por lo tanto Pvacio es un problema insoluble.
6.3. Funciones Computables En Teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales. Muchas de las funciones normalmente estudiadas en teoría de los números, y las aproximaciones a las funciones de valor real utilizan la recursión primitiva. Como ejemplo de ellas se tiene la suma, la división, el factorial, el enésimo primo, etc. De hecho, no es fácil definir una función que sea recursiva pero que no se pueda definir con recursión primitiva. Definición La recursión primitiva se define sobre los números naturales o sobre tuplas de números naturales. La aridad de una función es el número de sus argumentos. El conjunto de las funciones primitivas recursivas se define en base a las siguientes reglas: 1. La constante 0 es primitiva recursiva. 2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva. 3. Las funciones de proyección Pin, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas. 4. Composición: Dado f, una función primitiva recursiva de aridad k y k funciones primitivas recursivas de aridad l g0,…,gk-1, la composición de f con g0,…,gk-1, es decir, la función h(x0,…,xl-1) = f(g0(x0,…,xl-1),…,gk-1(x0,…,xl-1)), es primitiva recursiva. 5. Recursión primitiva: Dado f una función primitiva recursiva de aridad k y g una función primitiva recursiva de aridad k+2, la función de aridad k+1 definida como la función h donde h(0,x0,…,xk-1) = f(x0,…,xk-1) y h(S(n),x0,…,xk-1) = g(h(n,x0,…,xk-1),n,x0,…,xk-1), es primitiva recursiva. Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos. Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva. Ejemplo Suma de enteros Intuitivamente, se esperaría que la suma se comportase de la forma siguiente: suma(0,x)=x suma(n+1,x)=suma(n,x)+1 llevada esta función al esquema de las funciones primitivas queda así: suma(0,x)=P1¹(x) suma(S(n),x)=S(P1³(suma(n,x),n,x)) (donde P1³ es la función que recibe tres argumentos y retorna el primero de ellos) Se puede ver que P1¹ es la función identidad; se incluye su llamada para conformarse estrictamente al esquema de la recursión primitiva (función f del esquema). La composición de S con P1³, en el segundo caso también corresponde al esquema dado anteriormente (función g del esquema). Limitaciones Si bien la recursión primitiva parece poder expresar cualquier operación, en realidad sólo se cubre un subconjunto estricto de las funciones computables. Esto se verifica con una variante del argumento de diagonalización de Cantor. La prueba se puede esquematizar como sigue: Las funciones primitivas recursivas pueden ser ordenadas estrictamente asignándole a cada una de ellas un número. Este número es único para cada definición de función, si bien dos definiciones equivalentes de la misma función podrían tener diferente número asociado. El número asociado a cada función es calculable en el sentido de que puede ser definido en base a un mecanismo de cómputo como una función recursiva o una máquina de Turing. Se construye ahora una matriz donde las filas son las funciones primitivas recursivas de un solo argumento en orden según el número asociado y las columnas son los naturales. El valor de cada casilla es el resultado de la función de esa fila para el valor entero de esa columna. Se define ahora la función g(x) = S(n) donde n es el valor de la casilla de la fila y columna x. Cualquiera sea el valor de x, el valor de g(x) será distinto al de la función de la fila x al menos para el entero x. Por la construcción anterior, la función es computable, pero no recursiva primitiva, dado que es diferente a toda función primitiva para al menos un argumento entero. En conclusión, deben existir funciones computables que no son primitivas recursivas. Este mismo argumento se puede utilizar para cualquier conjunto de funciones totales computables, por lo que cualquier enumeración de funciones computables totales es necesariamente incompleta. En cambio, las funciones parciales computables sí pueden ser enumeradas de forma completa, por ejemplo enumerando el «programa» de su correspondiente máquina de Turing. Un ejemplo notable de función recursiva que no es primitiva recursiva es la función de Ackermann.