Decibilidad y Reducibilidad
Páginas: 13 (3148 palabras)
Publicado: 18 de abril de 2012
DECIBILIDAD
En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un númerofinito de pasos si la fórmula es válida o no en el sistema.
Por otra parte, una teoría decidible semánticamente, es un sistema axiomático donde existe un método para evidenciar que toda proposición verdadera en un modelo es decidible o no en el sistema en concreto.
Ejemplo: La Lógica proposicional es decidible, porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula quecombina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
La lógica de primer orden es sintácticamente decidible si se limita a predicados con un solo argumento (ver cálculo de predicados monódicos). Si seincluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa recursivamente enumerable es decidible sintácticamente. Por otro lado, toda teoría que incluya aritmética básica es no decidible sintácticamente.
Lenguajes Decidibles
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuenciade instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivo el estudio de problemas dedecisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en establecer una medida de la cantidad derecursos computacionales (en términos 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 una máquina de Turing que puede aceptar cualquier cadena wL y rechazar cualquier cadena w∉L.
* Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de Turing que puede aceptar cualquier cadena wL y rechazar cualquier cadena w∉L.
* Lenguajes recursivamenteenumerables: lenguajes estructurados por frases.
* Lenguajes recursivos: lenguajes decidibles por una máquina de Turing.
El problema del paro o de Halting
El problema del paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada.
Es decir, si existe una máquina MTh capaz de determinar si cualquier otra máquina se va a detener o no.
Es conocidoque el problema del alto es indecidible. Para demostrar que el problema del alto es indecidible tenemos que probar la siguiente afirmación:
NO existe una máquina MT NO existe una máquina MTh h que tomando como entrada cualquier máquina MT0, termine después de un tiempo finito y responda ‘SÍ’ cuando MT0 termine y ‘NO’ cuando MT0 no termine.
Si MTh existe el problema es decidible.
MTh
¿MT0...
En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un númerofinito de pasos si la fórmula es válida o no en el sistema.
Por otra parte, una teoría decidible semánticamente, es un sistema axiomático donde existe un método para evidenciar que toda proposición verdadera en un modelo es decidible o no en el sistema en concreto.
Ejemplo: La Lógica proposicional es decidible, porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula quecombina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
La lógica de primer orden es sintácticamente decidible si se limita a predicados con un solo argumento (ver cálculo de predicados monódicos). Si seincluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa recursivamente enumerable es decidible sintácticamente. Por otro lado, toda teoría que incluya aritmética básica es no decidible sintácticamente.
Lenguajes Decidibles
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuenciade instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo pueda ser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivo el estudio de problemas dedecisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en establecer una medida de la cantidad derecursos computacionales (en términos 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 una máquina de Turing que puede aceptar cualquier cadena wL y rechazar cualquier cadena w∉L.
* Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de Turing que puede aceptar cualquier cadena wL y rechazar cualquier cadena w∉L.
* Lenguajes recursivamenteenumerables: lenguajes estructurados por frases.
* Lenguajes recursivos: lenguajes decidibles por una máquina de Turing.
El problema del paro o de Halting
El problema del paro consiste en determinar si una máquina de Turing cualquiera se detendrá ante cualquier entrada dada.
Es decir, si existe una máquina MTh capaz de determinar si cualquier otra máquina se va a detener o no.
Es conocidoque el problema del alto es indecidible. Para demostrar que el problema del alto es indecidible tenemos que probar la siguiente afirmación:
NO existe una máquina MT NO existe una máquina MTh h que tomando como entrada cualquier máquina MT0, termine después de un tiempo finito y responda ‘SÍ’ cuando MT0 termine y ‘NO’ cuando MT0 no termine.
Si MTh existe el problema es decidible.
MTh
¿MT0...
Leer documento completo
Regístrate para leer el documento completo.