Teorias logicas, decidibilidad
Páginas: 2 (478 palabras)
Publicado: 10 de diciembre de 2010
Teorías Lógicas y Máquinas de Turing
Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de inferencia y un esquema de derivación. A partirde los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría. El conjunto de teoremas de la teoría forman un lenguaje formal.
Es posibledefinir una máquina de Turing tal que reconozca al lenguaje de los teoremas, este lenguaje es decidible y la teoría también lo es en consecuencia. Dicho en otras palabras, si el conjunto de teoremasvisto como un lenguaje es reconocido por una máquina de Turing, entonces la TL es decidible. Y viceversa.
Puede hablarse entonces de manera indistinta de Teorías lógicas o de lenguajes decidibles,como aquellos para los que existe una máquina de Turing capaz de reconocerlos. Luego, la correspondencia entre la sintaxis de una teoría lógica (lenguaje formal) y el reconocimiento simbólico de la mismapor parte de un autómata queda establecida.
Desde el punto de vista semántico, las interpretaciones de las cadenas del lenguaje se realizan ya sea por el intérprete ó bien por el compilador dellenguaje de programación en el cual se dan las instrucciones. Las cadenas que resultan en instrucciones realizadas por la computadora pueden considerarse interpretadas como verdaderas y por tantotienen, al menos, un modelo de la Teoría Lógica formada por tales cadenas.
Decidibilidad
En logica, el término decidible se refiere a la existencia de un metodo efectivo para determinar si un objeto(x,y,z,etc) es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo talque para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Explicacion
Para saber si un problema es decidible o no debe de...
Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de inferencia y un esquema de derivación. A partirde los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría. El conjunto de teoremas de la teoría forman un lenguaje formal.
Es posibledefinir una máquina de Turing tal que reconozca al lenguaje de los teoremas, este lenguaje es decidible y la teoría también lo es en consecuencia. Dicho en otras palabras, si el conjunto de teoremasvisto como un lenguaje es reconocido por una máquina de Turing, entonces la TL es decidible. Y viceversa.
Puede hablarse entonces de manera indistinta de Teorías lógicas o de lenguajes decidibles,como aquellos para los que existe una máquina de Turing capaz de reconocerlos. Luego, la correspondencia entre la sintaxis de una teoría lógica (lenguaje formal) y el reconocimiento simbólico de la mismapor parte de un autómata queda establecida.
Desde el punto de vista semántico, las interpretaciones de las cadenas del lenguaje se realizan ya sea por el intérprete ó bien por el compilador dellenguaje de programación en el cual se dan las instrucciones. Las cadenas que resultan en instrucciones realizadas por la computadora pueden considerarse interpretadas como verdaderas y por tantotienen, al menos, un modelo de la Teoría Lógica formada por tales cadenas.
Decidibilidad
En logica, el término decidible se refiere a la existencia de un metodo efectivo para determinar si un objeto(x,y,z,etc) es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo talque para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Explicacion
Para saber si un problema es decidible o no debe de...
Leer documento completo
Regístrate para leer el documento completo.