Proporção de problemas decidíveis

Considere os problemas de decisão declarados em uma linguagem formal "razoável". Digamos fórmulas na aritmética Peano de ordem superior com uma variável livre como quadro de referência, mas estou igualmente interessado em outros modelos de computação: equações diofantinas, problemas de palavras ao reescrever regras usando máquinas de Turing, etc. Uma resposta expressa em qualquer a formalização clássica seria boa, mas se você souber o quanto a escolha da formalização influencia a resposta, isso também seria interessante.

Dado o comprimento da declaração de um problema de decisão, podemos definir o número das demonstrações decidíveis de comprimento e o número das demonstrações indecidíveis de comprimento .$N$$D(N)$$N$$U(N)$$N$

O que se sabe sobre o crescimento relativo de e ? Em outras palavras, se eu tomar um problema de decisão bem formado aleatoriamente, qual é a probabilidade de ele ser decidido para um determinado comprimento de declaração?$U(N)$$D(N)$

_{Inspirado por esta pergunta, que pergunta se “a maioria dos problemas e algoritmos [são] decidíveis”. Bem, se você não filtrar por interesse, são eles?}

$U(N)$$D(N)$