Τι είναι το πρόβλημα απόφασης;

Ερ: Τι είναι το πρόβλημα απόφασης;

A: Ένα πρόβλημα απόφασης είναι μια ερώτηση σε κάποιο τυπικό σύστημα με απάντηση ναι ή όχι, που εξαρτάται από τις τιμές των παραμέτρων εισόδου.

Ερ: Σε ποια πεδία μελέτης εμφανίζονται τα προβλήματα απόφασης;

Α: Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ζητήματα αποφασισιμότητας.

Ερ: Ποια είναι η έννοια της αποφασισιμότητας;

Α: Η αποφασισιμότητα αναφέρεται στο ερώτημα της ύπαρξης μιας αποτελεσματικής μεθόδου για τον προσδιορισμό της ύπαρξης κάποιου αντικειμένου ή της συμμετοχής του σε ένα σύνολο.

Ερ: Είναι όλα τα προβλήματα στα μαθηματικά αποφασίσιμα;

Α: Όχι, ορισμένα από τα πιο σημαντικά προβλήματα στα μαθηματικά είναι μη αποφασίσιμα.

Ερ: Τι είναι ένα μη αποφασίσιμο πρόβλημα;

Α: Ένα μη αποφασίσιμο πρόβλημα είναι ένα πρόβλημα για το οποίο δεν υπάρχει αλγόριθμος που να μπορεί πάντα να δώσει μια απάντηση ναι ή όχι μέσα σε πεπερασμένο χρονικό διάστημα.

Ερ: Η απάντηση σε ένα πρόβλημα απόφασης είναι πάντα ναι ή όχι;

Α: Ναι, η απάντηση σε ένα πρόβλημα απόφασης είναι πάντα ναι ή όχι.

Ερ: Από τι εξαρτάται η απάντηση σε ένα πρόβλημα απόφασης;

Α: Η απάντηση σε ένα πρόβλημα απόφασης εξαρτάται από τις τιμές των παραμέτρων εισόδου.