Współczynnik rozstrzygalnych problemów

20

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 D ( N ) z rozstrzygalnych oświadczenia o długości N oraz liczbę U ( N ) z nierozstrzygalnych oświadczenia o długości N .ND(N)NU(N)N

Co wiadomo na temat względnego wzrostu i D ( N ) ? 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?

Gilles „SO- przestań być zły”
źródło
4
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'
5
D(N)
1
powiązane pytanie: jakie jest prawdopodobieństwo rozstrzygnięcia losowej maszyny Turinga w stanie n?
Kaveh,
2
Oto podobne pytanie na temat matematyki : Gęstość zatrzymywania maszyn Turinga
Kaveh

Odpowiedzi:

2

U(N)D(N)

vzn
źródło
1
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