W teorii obliczeń terminy "Zapewnialny i Rozstrzygalny" są wymierne? Czy mają na myśli to samo?Czy zapewnia == Rozstrzygające?
Na przykład często widzisz pytanie, czy coś jest do udowodnienia, określane jako problem decyzyjny (Das Entscheidungsproblem).
Są różne. W rzeczywistości odnoszą się one do zupełnie innych obszarów.
Rozstrzygające oznacza, że problem decyzyjny może zostać rozwiązany dla wszystkich możliwych danych wejściowych przez maszynę Turinga, która zgłasza "zaakceptuj" lub "odrzuć".
Provable oznacza, że oświadczenie matematyczne może być udowodnione przez, dobrze, dowód matematyczny.
W rzeczywistości nie można porównywać "rozstrzygalnych" i "możliwych do udowodnienia", ponieważ te atrybuty odnoszą się do zupełnie innych rzeczy.
Musisz udowodnić, że decyzja maszyny działa poprawnie;) – Dario
Może odpowiednie pytanie dla mathoverflow.net? –
Myślałem o tym, ale jako Comp. Kurs teorii (i złożoności) można znaleźć na prawie wszystkich kursach CS \ SE, które według mnie byłyby bardziej odpowiednie. –