decidibilidad

decidibilidad

 
f. lóg. Posibilidad de un cálculo de tener unos procedimientos decisorios para establecer si una fórmula cualquiera es válida o no en el sistema.
Ejemplos ?
Rabin, un colega de Princeton, titulado Finite Automata and Their Decisión Problem (Autómatas Finitos y el Problema de su Decidibilidad), que introdujo la idea de las máquinas no determinísticas en el campo de la teoría de autómatas.
Conservación: una prueba de que ningún resultado acerca de "objetos reales" obtenida usando razonamiento sobre "objetos ideales" (como los conjuntos incontables) puede ser probado sin usar objetos ideales. Decidibilidad: debería haber un algoritmo para decidir la verdad o falsedad de cualquier afirmación matemática.
En 1915, Leopold Löwenheim demostró la consistencia, completitud semántica y decidibilidad de la lógica de primer orden monádica.
Nació en Misheronski, cerca de la capital Moscú y falleció en Nobosibirsk. Destacado por sus trabajos en decidibilidad en muchos grupos algebraicos.
En los primeros años 1960s, trabajó en problemas de decidibilidad de teorías elementales de varias estructuras algebraicas. Demostró la indecidibilidad de la teoría elemental de grupos finitos, de los grupos nilpotentes libres, de los grupos solubles libres y muchos otros casos.
También probó que una clase de álgebras localmente libres tiene una teoría de decidibilidad. Recibió muchos premios, entre otros::Premio Stalin en 1946:Premio Lenin en 1964.
Erigió también el "Seminario de Álgebra y Lógica", atendido por varios estudiantes. Seminario que dio frutos en teoría de modelos y teorías elementales de de de decidibilidad.
Comparado con el tipado estático, o sistema de enlazado temprano, el tipado dinámico es más flexible (debido a las limitaciones teóricas de la decidibilidad de ciertos problemas de análisis de programas estáticos, que impiden el mismo nivel de flexibilidad que se consigue con el tipado estático), a pesar de ejecutarse más lentamente y ser más propensos a contener errores de programación.
En las palabras de Paul Samuelson: "es mejor tener un modelo con bases inexactas que le da un buen agarre para manejar la realidad que esperar por una mejor fundación o seguir utilizando un modelo con buenas bases pero que no es útil o relevante para explicar los fenómenos que tenemos que explicar" La posición contraria, generalmente más aceptada, por lo menos a niveles académicos, se preocupa con cuestiones metodologicas de la Teoría formal, tales como Consistencia (lógica), Decidibilidad, reglas de inferencias; tipos de método, etc.
Es el caso de la decidibilidad en mathcal ALC y en todas sus extensiones que se obtienen añadiendo constructores que en la LPO se pueden expresar con dos variables.
Acerca de los conjuntos decidibles, Alonzo Church obtuvo resultados importantes, logrando demostrar la indecidibilidad de la lógica de predicados en todos los órdenes. El concepto de recursividad en este contexto es equivalente al de computabilidad y decidibilidad.