Mientras leía la tesis doctoral de Balder ten Cate (2005). Teoría de modelos para lenguajes modales extendidos. Encontré un teorema que dice
2.6.4 Teorema. El problema de la satisfacción del marco para las fórmulas modales es altamente indecidible, de hecho no es analítico.
Mi pregunta es: ¿Qué significa eso de altamente indecidible y no analítico?
Por "indecidible", el autor quiere decir que el problema tiene un grado de Turing distinto de cero: no hay ningún algoritmo que decida el problema correctamente.
Por "no analítico", el autor quiere decir que el problema no es clasificable en el jerarquía analítica . Esto equivale a decir que no es definible por una fórmula de la aritmética de segundo orden.
En el Apéndice B de la tesis parece haber un resumen de esto.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
