Rasio masalah yang dapat diputuskan

Pertimbangkan masalah keputusan yang dinyatakan dalam beberapa bahasa formal yang "masuk akal". Katakanlah rumus dalam aritmetika Peano tingkat tinggi dengan satu variabel bebas sebagai kerangka acuan, tapi saya sama-sama tertarik pada model perhitungan lain: persamaan Diophantine, masalah kata dari aturan penulisan ulang menggunakan mesin Turing, dll. Jawaban dinyatakan dalam setiap formalisasi klasik akan baik-baik saja, meskipun jika Anda tahu seberapa banyak pilihan formalisasi memengaruhi jawabannya, itu juga akan menarik.

Mengingat panjang dari pernyataan masalah keputusan, kita dapat menentukan jumlah dari pernyataan panjang yang dapat ditentukan dan jumlah dari panjang dapat ditentukan .$N$$D(N)$$N$$U(N)$$N$

Apa yang diketahui tentang pertumbuhan relatif dan ? Dengan kata lain, jika saya mengambil masalah keputusan yang terbentuk secara acak, berapakah probabilitas keputusan tersebut dapat ditentukan untuk panjang pernyataan yang diberikan?$U(N)$$D(N)$

_{Terinspirasi oleh pertanyaan ini yang menanyakan apakah “sebagian besar masalah dan algoritma dapat dipilih”. Nah, jika Anda tidak memfilter menurut minat, bukan?}

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