Verhältnis der entscheidbaren Probleme

Betrachten Sie Entscheidungsprobleme, die in einer „vernünftigen“ formalen Sprache angegeben sind. Sagen wir, Formeln in Peano-Arithmetik höherer Ordnung mit einer freien Variablen als Bezugsrahmen, aber ich interessiere mich auch für andere Berechnungsmodelle: diophantische Gleichungen, Wortprobleme durch das Umschreiben von Regeln mit Turing-Maschinen usw. Eine in any ausgedrückte Antwort Eine klassische Formalisierung wäre in Ordnung, aber wenn Sie wissen, wie sehr die Wahl der Formalisierung die Antwort beeinflusst, wäre dies auch interessant.

Ausgehend von der Länge der Aussage eines Entscheidungsproblems können wir die Anzahl D ( N ) entscheidbarer Aussagen der Länge N und die Anzahl U ( N ) unentscheidbarer Aussagen der Länge N definieren .$N$$D(N)$$N$$U(N)$$N$

Was ist über das relative Wachstum von und D ( N ) bekannt ? Mit anderen Worten, wenn ich ein wohlgeformtes Entscheidungsproblem zufällig nehme, wie groß ist die Wahrscheinlichkeit, dass es für eine bestimmte Anweisungslänge entscheidbar ist?$U(N)$$D(N)$

_{Inspiriert von dieser Frage, die fragt, ob „die meisten Probleme und Algorithmen entscheidbar sind“. Gut, wenn Sie nicht nach Interesse filtern, sind das dann?}

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