Decibilidad

Decidibilidad
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 proposicion 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 se incluyenpredicados 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
Indecidibilidad
Indecidibilidad, la cualidad de lo indecidible (lo contrario de la decidibilidad y lo decidible), puede referirse a:
En lógica matemática:
Los denominadosTeoremas de la incompletitud de Gödel (articulo de 1931 de Kurt Gödel Sobre sentencias formalmente indecidibles de "Principia Mathematica" y sistemas afines). Véase también Incompletitud de Gödel e indecisión doxástica.
La cualidad de un problema de decisión (recursivamente) indecidible, que no puede decidirse por ningún algoritmo, como el problema de la parada de Alan Turing; véase también problemaindecidible.
A veces se emplea indecidible como sinónimo de independiente en lógica matemática (una fórmula en lógica matemática es independiente de una teoría lógica si ni la fórmula ni su negación puede ser probada dentro de la teoría).
Otros usos
Objeto imposible (o figura indecidible).
Conjunto recursivamente enumerable (o conjunto semidecidible).
No conviene confundir con indecible o loinefable (lo que no se puede decir o lo que no se puede explicar con palabras)

-------------------------------------------------
Lenguaje recursivo
Un lenguaje recursivo en matemáticas, lógica e informática, es un tipo de lenguaje formal que también es llamado recursivo, decidible o Turing-decidible. Se caracterizan porque para cada uno de ellos existe una máquina de Turing que aceptarácualquier palabra del lenguaje y parará siempre.

El problema de “Halting”
El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)
Básicamente, Turing definió las bases de las computadoras modernas y planteo un problema sobreellas, llegando a la conclusión de que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (Halting problem); el problema de saber si un problema se cuelga cuando corre en la computadora. Turing demostró que el problema de la detención es indicidible, es decir, demostró que había problemas que una maquina no podía resolver.
Es meritorio el hecho que gracias a la equivalenciasde maquinas de Turing y computadoras, se haya determinado que existen cálculos que no pueden ser detenidos en un tiempo razonable en ninguna computadora imaginable, o incluso, que no puede resolverse en lo absoluto, por ejemplo el problema de correspondencia de Post o el problema de predecir si una maquina de Turing cualquiera va a llegar a un estado final (conocido como el problema de Halting...