Teoría de decidibilidad

Teoría de 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 oteorí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 unnúmero finito de pasos si la fórmula es válida o no en el sistema. La lógica de primer orden es decidible si se limita a predicados con un solo argumento. Si se incluyen predicados con dos o másargumentos, no es decidible.
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 decidibleo no en el sistema en concreto. También toda teoría completa recursivamente enumerable es decidible. Por otro lado, toda teoría que incluya aritmética básica es no decidible.
En otras palabras sepuede decir que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito (quiere decir que deben estar establecidos cada uno de los estados que lo forman, en otras palabras eltiempo debe estar señalado) si una cadena cualquiera es un teorema o no lo es.
También hay que mencionar que en 1936, un matemático británico, Alan Turing, publica un ensayo titulado: “Acerca de NúmerosComputables con una Aplicación al Problema de le Decidibilidad” (de Hilbert). En ese ensayo, introduce su máquina “pensante” primitiva, madre de la ciencia de la computación.

Turing demuestra queproblemas computables pueden ser resueltos por una máquina con una cinta infinitamente larga, subdividida en pequeñas celdas cuadradas y con un dispositivo con un número definido de estados capaz de“leer” los símbolos “escritos” sobre esa cinta. En función del símbolo leído y del “estado” de la máquina, se puede escribir otro símbolo.

Puntos importantes:
- Un problema es decidible si es...