– Ένα πρόβλημα απόφασης P λέγεται ότι είναι ημι-αποφασίσιμο (δηλαδή, έχει έναν ημι-αλγόριθμο) εάν η γλώσσα L όλων των περιπτώσεων ναι στο P είναι r.e. – (Πρόβλημα ισοδυναμίας για DFA) Δεδομένων δύο DFA, δέχονται την ίδια γλώσσα; Απόδειξη: Ανακαλέστε το επιχείρημα του Κάντορ από την Πρώτη Διάλεξη.
Όταν ένα πρόβλημα λέγεται ότι μπορεί να λυθεί;
Ημι-αποφασίσιμα προβλήματα είναι εκείνα για το τα οποία μια μηχανή Turing σταματά στην είσοδο που είναι αποδεκτή από αυτήν, αλλά μπορεί είτε να σταματήσει είτε να κάνει βρόχο για πάντα στην είσοδο που απορρίπτεται από τη Μηχανή Turing. Τέτοια προβλήματα ονομάζονται προβλήματα Turing αναγνωρίσιμα.
Τι είναι μερικώς επιλύσιμο πρόβλημα;
Ορισμός: Μία της οποίας η συσχετισμένη γλώσσα είναι μια αναδρομικά απαριθμήσιμη γλώσσα. Ομοίως, υπάρχει ένας αλγόριθμος που σταματά και εξάγει 1 για κάθε περίπτωση που έχει απάντηση "ναι", αλλά για περιπτώσεις που έχουν απάντηση "όχι" επιτρέπεται είτε να μην σταματήσει είτε να σταματήσει και να εξάγει 0.
Είναι μερικώς επιλύσιμη η διακοπή του προβλήματος;
Ο Alan Turing απέδειξε το 1936 ότι ένας γενικός αλγόριθμος που εκτελείται σε μια μηχανή Turing που λύνει το πρόβλημα διακοπής για όλα τα πιθανά ζεύγη εισόδου προγράμματος δεν μπορεί απαραίτητα να υπάρξει. Ως εκ τούτου, το πρόβλημα παύσης δεν μπορεί να επιλυθεί για τις μηχανές Turing.
Γιατί το πρόβλημα διακοπής είναι ημι-αποφάσσιμο;
Μια γλώσσα λέγεται ότι είναι ημι-αποφασίσιμη εάν υπάρχει μια μηχανή Turing η οποία σταματάει εάν μια λέξη ανήκει στη γλώσσα (περιπτώσεις ΝΑΙ) και μπορεί να απορρίψει ή να πάει σε άπειρο βρόχο αν η λέξη δεν ανήκει στη γλώσσα (ΟΧΙ περίπτωση).
