Considere los problemas de decisión establecidos en un lenguaje formal "razonable". Digamos fórmulas en aritmética de Peano de orden superior con una variable libre como marco de referencia, pero estoy igualmente interesado en otros modelos de cómputo: ecuaciones de diofantina, problemas de palabras por reescribir reglas usando máquinas de Turing, etc. Una respuesta expresada en cualquier la formalización clásica estaría bien, aunque si sabes cuánto influye la elección de la formalización en la respuesta, eso también sería interesante.
Dada la longitud de la declaración de un problema de decisión, podemos definir el número D ( N ) de los enunciados indecidibles de longitud N y el número T ( N ) de los enunciados indecidibles de longitud N .
¿Qué se sabe sobre el crecimiento relativo de y D ( N ) ? En otras palabras, si tomo un problema de decisión bien formado al azar, ¿cuál es la probabilidad de que sea decidible para una longitud de enunciado dada?
Inspirado por esta pregunta que pregunta si "la mayoría de los problemas y algoritmos [son] decidibles". Bueno, si no filtra por interés, ¿verdad?
fuente
Respuestas:
fuente