Współczynnik rozstrzygalnych problemów

Rozważ problemy decyzyjne sformułowane w jakimś „rozsądnym” języku formalnym. Powiedzmy, że wzory w arytmetyce Peano wyższego rzędu z jedną wolną zmienną jako ramą odniesienia, ale równie interesują mnie inne modele obliczeń: równania diofantyczne, problemy słowne z przepisywania reguł za pomocą maszyn Turinga itp. Odpowiedź wyrażona w dowolnym klasyczna formalizacja byłaby w porządku, ale jeśli wiesz, jak bardzo wybór formalizacji wpływa na odpowiedź, byłoby to również interesujące.

Biorąc Length zestawienia problemu decyzyjnego, możemy zdefiniować numer z rozstrzygalnych oświadczenia o długości oraz liczbę z nierozstrzygalnych oświadczenia o długości . $N$ $D(N)$ $N$ $U(N)$ $N$

Co wiadomo na temat względnego wzrostu i ? Innymi słowy, jeśli losowo podejmę dobrze sformułowany problem decyzyjny, jakie jest prawdopodobieństwo rozstrzygnięcia go dla danej długości instrukcji? $U(N)$ $D(N)$

_{Zainspirowany tym pytaniem, które brzmi „czy większość problemów i algorytmów jest możliwych do rozstrzygnięcia”. Cóż, jeśli nie filtrujesz według zainteresowań, prawda?}

computability undecidability

— Gilles „SO- przestań być zły”
źródło

Pytasz więc w zasadzie, jak duża część opisywalnych języków jest rozstrzygalna? Jeśli weźmiemy pod uwagę wszystkie języki, wówczas ta frakcja jest oczywiście równa 0, ponieważ istnieje niezliczona ilość języków.

— Alex ten Brink

@AlextenBrink Mówiąc dokładniej, pytam, jak duża część opisów języków jest rozstrzygającymi językami. Może mieć znaczenie, że liczba równoważnych opisów języka jest skorelowana z jego rozstrzygalnością. PS Nie wahaj się edytować mojego pytania, jeśli uważasz, że nie jest ono wyraźnie wyrażone.

— Gilles 'SO - przestań być zły'

D (N)

$D(N)$

powiązane pytanie: jakie jest prawdopodobieństwo rozstrzygnięcia losowej maszyny Turinga w stanie n?

— Kaveh,

Oto podobne pytanie na temat matematyki : Gęstość zatrzymywania maszyn Turinga

— Kaveh

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

— vzn
źródło

Obie funkcje są oczywiście w ogóle nieobliczalne. Jednak nie jest wykluczone znalezienie wyraźnych granic ich asymptotycznego stosunku, tak jak można znaleźć granice liczby nieściśliwych łańcuchów wielkości n.

— cody