Decibilidad y Reducibilidad

7/29/2019 Decibilidad y Reducibilidad

1/17

DECIBILIDAD

En lgica, el trmino decidible se refiere a la existencia de un mtodoefectivo para determinar si un objeto es miembro de un conjunto defrmulas.

Un sistema lgico o teora es decidible sintcticamente si el conjunto detodas las frmulas vlidas en el sistema es decidible. Es decir, existe unalgoritmo tal que para cada frmula del sistema es capaz de decidir en unnmero finito de pasos si la frmula es vlida o no en el sistema.Por otra parte, una teora decidible semnticamente, es un sistemaaxiomtico donde existe un mtodo para evidenciar que toda proposicinverdadera en un modelo es decidible o no en el sistema en concreto.

Ejemplo: La Lgica proposicional es decidible, porque existe para ella unalgoritmo; la tabla de verdad tal que para cada frmula que combina Mformulas atmicas, hay un nmero mximo N = 2M de pasos tal que trascompletar estos N pasos el algoritmo siempre decidir si la frmula esvlida o no. Cada "paso" del algoritmo ha sido definido como una lnea dela tabla de verdad.La lgica de primer orden es sintcticamente decidible si se limita a

predicados con un solo argumento (ver clculo de predicados mondicos).Si se incluyen predicados con dos o ms argumentos, no es decidible.

Toda teora completa recursivamente enumerable es decidiblesintcticamente. Por otro lado, toda teora que incluya aritmtica bsica esno decidible sintcticamente.

Lenguajes Decidibles

Existen problemas que no pueden ser resueltos por una computadora,dado que las computadoras solamente pueden ejecutar algoritmos, estoes secuencia de instrucciones universalmente precisas y entendibles queresuelven cualquier instancia de problemas computacionales definidosrigurosamente.
http://es.wikipedia.org/wiki/Sistema_axiom%C3%A1ticohttp://es.wikipedia.org/wiki/Sistema_axiom%C3%A1ticohttp://es.wikipedia.org/wiki/L%C3%B3gica_proposicionalhttp://es.wikipedia.org/wiki/Tabla_de_verdadhttp://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_ordenhttp://es.wikipedia.org/w/index.php?title=C%C3%A1lculo_de_predicados_mon%C3%B3dicos&action=edit&redlink=1http://es.wikipedia.org/w/index.php?title=Teor%C3%ADa_completa&action=edit&redlink=1http://es.wikipedia.org/w/index.php?title=Recursivamente_enumerable&action=edit&redlink=1http://es.wikipedia.org/w/index.php?title=Recursivamente_enumerable&action=edit&redlink=1http://es.wikipedia.org/w/index.php?title=Teor%C3%ADa_completa&action=edit&redlink=1http://es.wikipedia.org/w/index.php?title=C%C3%A1lculo_de_predicados_mon%C3%B3dicos&action=edit&redlink=1http://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_ordenhttp://es.wikipedia.org/wiki/Tabla_de_verdadhttp://es.wikipedia.org/wiki/L%C3%B3gica_proposicionalhttp://es.wikipedia.org/wiki/Sistema_axiom%C3%A1ticohttp://es.wikipedia.org/wiki/Sistema_axiom%C3%A1tico


2/17

No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida

formalmente. El correspondiente modelo matemtico se llama mquina de

Turing (Alan Turing, 1936).

La teora de computabilidad tiene como objetivo el estudio de problemasde decisin, con el fin de determinar si los mismos son tericamente

decidibles.

Los problemas se pueden clasificar desde el punto de vista de la teora de

computabilidad en resolubles y no resolubles. Los problemas resolubles

son objeto de estudio de la teora de complejidad computacional.

En el contexto de complejidad computacional, el inters est centrado en

establecer una medida de la cantidad de recursos computacionales (entrminos de tiempo y/o espacio) necesarios para resolver un determinado

problema o equivalentemente reconocer un lenguaje.

Los problemas resolubles se subdividen en tratables e intratables. Los

problemas tratables son aquellos para los cuales existe un algoritmo

eficiente que los resuelve. Los intratables son aquellos para los cuales no

se conoce (o tal vez no exista) un algoritmo eficiente que los resuelva.

Lenguaje decidible: es aquel lenguaje L para el cual existe unamquina de Turing que puede aceptar cualquier cadena wL y

rechazar cualquier cadena wL.

Lenguaje aceptable: es aquel lenguaje L para el cual no existeninguna mquina de Turing que puede aceptar cualquier cadena w

L y rechazar cualquier cadena wL.

Lenguajes recursivamente enumerables: lenguajes estructuradospor frases.

Lenguajes recursivos: lenguajes decidibles por una mquina deTuring.

El problema del paro o de Halting


3/17

El problema del paro consiste en determinar si una mquina de Turing

cualquiera se detendr ante cualquier entrada dada.

Es decir, si existe una mquina MTh capaz de determinar si cualquier otra

mquina se va a detener o no.

Es conocido que el problema del alto es indecidible. Para demostrar que el

problema del alto es indecidible tenemos que probar la siguiente

afirmacin:

NO existe una mquina MT NO existe una mquina MTh h que tomando

como entrada cualquier mquina MT0, termine despus de un tiempo

finito y responda S cuando MT0termine y NO cuando MT0 no termine.

Si MTh existe el problema es decidible.

Cuando MT0 termina

MT0

Cuando MT0 no termina

Si MTh NO existe el problema es indecidible

Por contradiccin demostraremos que no existe una mquina MTh que

resuelva el problema del alto.

Hiptesis:

Supondremos que existe MTh.

MTh

MT0 termina?

SI

NO


4/17

Al final llegaremos a una contradiccin derivada de esta hiptesis.

Construyamos una nueva mquina MTs que se comporte de la siguiente

manera:

La nueva mquina MTs tomar como entrada una mquina dadaMT0.

MTs ejecutar la mquina MTh y le dar como entrada la mquinaMT0. Por hiptesis, MTh terminar en algn momento y responder

S o NO (segn MT0 termine o no).

Si MTh dice S, entonces MTs entra en un ciclo infinito y no termina. Si MTh dice NO, entonces MTs se detiene inmediatamente (la salida

no importa).

MT MTs termina cuando es la entrada de s misma.


5/17

Por hiptesis, MTh responder S ya que supusimos que MTs termina.


6/17

Una vez que MTh responde S, comienza un ciclo infinito.

Esto implica que la suposicin de que MTs termina al aplicarse a s misma,

implica que MTs no termina!


7/17

|

REDUCIBILIDAD

Se dice que un problema L1 se reduce en tiempo polinomial determinstico

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: Unaproblema 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 determinstico.

Problemas insolubles para la teora de lenguajes.

Sea el problema Palguna el siguiente problema:

Pacept: Existe un procedimiento efectivo capaz de determinar si unamquina 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


8/17

lugar debido a que la solubilidad de Palguna implica la solubilidad de Pdet.

Expresado de otra manera, demostramos que Pdet se reduce a Palguna.

Demostracin:

Supongamos que Palguna es un problema de decisin soluble. Al ser un

problema soluble, entonces existe un procedimiento efectivo (o mquina

universal de Turing), Alguna, que resuelve Palguna. Alguna toma como

datos de entrada la descripcin de una mquina 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 mquina

universal de Turing) Detencin.

La mquina Detencin recibe como entrada un par (T,), el problema

Palguna solo tiene como entrada una mquina 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 detencin. Este

proceso adicional se lleva a cabo en la mquina universal X que realiza lo

siguiente:


9/17

a) Recibe como dato de entrada la mquina de Turing T y la cadena .b)Construye una mquina de Turing T tal que:

i. Para la cadena se comporta como la mquina de Turing T.ii. Para toda cadena que no sea la nueva mquina T nunca se

detiene o cicla indefinidamente.

Combinando las mquinas universales Alguna y X, tenemos la mquina

universal Detencin que tiene el siguiente comportamiento:

1. Detencin recibe como entrada el par (T, ).2. La mquina universal Detencin utiliza X, la cual a partir de T y

construye la nueva mquina de Turing T.

3. La mquina de Turing T obtenida en el paso anterior es ingresada a lamquina universal Alguna.

4. Si la respuesta de Alguna es 1 entonces T se detiene para algunacadena. De la manera en la que construimos T esa cadena

necesariamente es la cadena (ya que para el resto sabemos que la

mquina siempre cicla) como el comportamiento de T frente a la

cadena es el mismo que tiene la mquina T entonces podemos

afirmar que T se detiene sobre y que por lo tanto Detencin 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 poda detenerse era y que el comportamiento frente a

esta cadena era el mismo que el de la mquina T. Podemos

entonces afirmar, que la mquina de Turing T tampoco se detiene

frente a la cadena y que por lo tanto la respuesta que emite

Detencin es igual a 0.

Conclusin:

La mquina universal Detencin retorna 1 (T se detiene sobre ) siAlguna retorna 1 (T se detiene sobre alguna cadena).

La mquina universal Detencin retorna 0 (T no se detiene sobre )si Alguna retorna 0 (T se detiene sobre ninguna cadena).


10/17

Hemos mostrado como construir la mquina universal Detencin que

resuelve el problema de la detencin a partir de la mquina universal

Alguna que resuelve un problema que supusimos soluble. Sabemos por

hiptesis que el problema de la detencin es un problema insoluble, por lo

tanto la solucin encontrada mediante la mquina universal Detencin 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 construccin

X existe, luego Alguna no puede existir. Podemos entonces concluir que

Palguna es un problema no-soluble.

Un problema simple Insoluble.

Sea el problema Pacept el siguiente problema:

Pacept: Existe un procedimiento efectivo capaz de determinar si unamquina de Turing acepta una determinada cadena ?

Otra manera de formular el problema sera:

Pacept: Existe un procedimiento efectivo capaz de determinar si unadeterminada cadena, , pertenece al lenguaje que reconoce lamquina 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.

Demostracin:

Supongamos que Pacept es un problema de decisin soluble. Al ser un

problema soluble, entonces existe un procedimiento efectivo (o mquina

universal de Turing), X, que resuelve


11/17

Pacept. X toma como datos de entrada la descripcin de una mquina 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 mquina

universal de Turing) Y

La mquina 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 detencin. Este proceso adicional se lleva a cabo en la mquina universalX que realiza lo siguiente:

a) Recibe como dato de entrada la mquina de Turing T.b)Modifica T manteniendo su definicin de quntuplas pero indicando

que todos los estados son aceptadores.


12/17

c) Retorna la mquina modificada con el nombre T.Combinando las mquinas X y X, tenemos la mquina universal Y que

tiene el siguiente comportamiento:

1. Y recibe como entrada el par (T, ).2. La mquina universal Y utiliza X, la cual a partir de T construye T.3. El par (T, ) es ingresado a la mquina 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 nose 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 .

Conclusin:

La mquina universal Yretorna 1 (

Tse detiene sobre ) siX retorna 1

(Tacepta ).

La mquina universal Y retorna 0 (T no se detiene sobre ) si Xretorna 0 (Tno acepta ).

Hemos mostrado como construir la mquina universal Y que resuelve el

problema de la detencin a partir de la mquina universal X que resuelve

un problema que supusimos soluble.

Sabemos por hiptesis que el problema de la detencin es un problemainsoluble, por lo tanto la solucin encontrada mediante la mquina

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 construccin X existe, luego X no. Podemos entonces concluir

que Pacept es un problema no-soluble.


13/17

Funcin computable

Las funciones computables son el objeto bsico de estudio de la teora de

la computabilidad y consisten en las funciones que pueden ser calculadas

por una mquina de Turing. Las funciones computables son una

formalizacin de la nocin intuitiva de algoritmo y segn la Tesis de

Church-Turing son exactamente las funciones que pueden ser calculadas

con una mquina de clculo. La nocin de la computabilidad de una

funcin puede ser relativizada a un conjunto arbitrario de nmeros

naturales A, o equivalentemente a una funcin arbitraria f de los naturalesa los naturales, por medio de mquinas de Turing extendidas con un

orculo por A o f. Tales funciones puede ser llamados A-computable o f-

computable respectivamente. Antes la definicin precisa de una funcin

computable los matemticos usaban el trmino informal efectivamente

computable. Las funciones computables son usadas para discutir

computabilidad sin referirse a ningn modelo de computacin concreto,

como el de la mquina de Turing o el de la mquina de registros. Los

axiomas de Blum pueden ser usados para definir una teora de complejidad

computacional abstracta sobre el conjunto de funciones computables.

Las funciones computables son las que se calculan por programas-while .

Si P es un programa-while y es la lista de variables en P entonces

consideraremos a las primeras variables como variables de entrada y a las

ltimas como de salida, de manera slo un poco ms precisa, para

consideraremos


14/17

El programa Pcalcula, o computa, a la funcin

donde

En este caso definimos,

En adelante omitiremos los subndices n,m y k. escomputable si existe un programa-while tal que f=fP.

Segn la Tesis de Church-Turing, la clase de funciones computables es

equivalente a la clase de funciones definidas por funciones recursivas,

clculo lambda, o algoritmos de Markov.

Alternativamente se pueden definir como los algoritmos que pueden ser

calculados por una mquina de Turing, una mquina de Post, o una

mquina de registros.

En teora de la complejidad computacional, el problema de determinar la

complejidad de una funcin computable esta conocido como un problema

de funciones.


15/17

Una funcin parcial

se llama parcialmente computable si el grfico de f es un

conjunto recursivamente enumerable. El conjunto de funciones

parcialmente computables con un parmetro es normalmente escritoo si el nmero de parmetros puede deducirse del contexto.

Una funcin total

se llama computable si el grfico de f es un conjunto recursivo.

El conjunto de funciones totalmente computables con un parmetro

normalmente se escribe o

Una funcin computable f se llama predicado computable si es una funcin

con valor booleano, es decir .

Propiedades

El conjunto de las funciones computables es numerable. Si f y g son funciones computables entonces f + g, fg y fog son

funciones computables.

Las funciones computables son definibles aritmticamente. Una funcin con valor booleano f es un predicado computable si y

slo si el lenguaje es recursivo.

Otra aportacin remarcable fue la definicin de una Mquina Universal(MU):

Una Mquina de Turing que emula el comportamiento de cualquier otra

MT. La MU lee de la cinta la descripcin finita de la mquina a emular M y

una entrada para dicha mquina. Entonces produce la misma salida que M


16/17


17/17

existen, en la esperanza de que no fueran completos respecto reducciones

de Turing. La idea era procurar que los complementarios fueran lo ms

delgados posible en cierto sentido intuitivo: en un inmune no cabe un

recursivamente enumerable y en un hiperinmune (complementario de un

hipersimple) el siguiente elemento esta siempre demasiado lejos para loque puede lograr enumerar una funcin recursiva. Sin embargo ms

adelante se estableci que existen hiper-hipersimples que son T completos

e incluso que existen recursivamente numerables maximales respecto a la

inclusin, y por tanto con complementario lo ms delgado posible en

este sentido intuitivo, y que son T completos.

La solucin finalmente requiri un concepto tcnico nuevo, las

construcciones por mtodos de prioridad, que extendieron otra de las

varias contribuciones de Post. Merece la pena comentar que actualmente

existen varias demostraciones diferentes, algunas de las cuales pueden

considerarse la culminacin del programa estructural de Post; pese a lo

cual, los mtodos de prioridad han de verse como el camino apropiado de

solucin.

Decibilidad y Reducibilidad

Documents

Transcript of Decibilidad y Reducibilidad