Reducibilidad

INTRODUCCIÓN:
En este trabajo de investigación se desarrollo el tema de Reducibilidad de la sexta unidad de la materia teoría de la computación, la cual se divide en subtemas que tiene en si cierta relación donde se manejan problemas como el tema lo dice simples, los cuales responden a una pregunta proporcionando un resultado.
Estos temas se explican a continuación.

Unidad 6:Reducibilidad

6.1 Problemas Insolubles Teoría de Lenguajes

6.2 Un Problema simple Insoluble

6.3 Funciones Computables

6.4 Reducibilidad De Turing
REDUCIBILIDAD
Si V tiene un subespacio propio no trivial W tal que W está contenido en V y es estable por la representación ρ, entonces la representación se dice reducible. Una representación reducible se puede expresar como una suma directa desubrepresentaciones (Teorema de Maschke) (solamente para los grupos finitos son las representaciones reducibles necesariamente descomponibles!). Si V no tiene ningún tal subespacio, 6rho; se dice una representación irreducible.
6.1.-PROBLEMAS INSOLUBLES 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 unalgoritmo 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 reducea encontrar el menor
• Sabemos que existe Menor(i; j), que devuelve
el elemento menor del segmento del arreglo
A[i, j].
30-nov-05 28
Ejemplo
PROCEDIMIENTO Ordena(A; n)
COMIENZA
PARA i =1 A n HAZ
j = Menor(i; n)
intercambia(i; j)
FINPARA
TERMINA

6.2.-UN PROBLEMA SIMPLE INSOLUBLE

Sea el problema Palguna el siguiente problema:
Pacept: ¿Existe un procedimiento efectivo capaz dedeterminar 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 unproblema 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 deAlguna, 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 ciclaindefinidamente.

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...