Διαφορά μεταξύ των αναθεωρήσεων του «Θεωρία υπολογισιμότητας»

Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
Όπως τις:
 
===== '''<u>Μία προς μία αναγωγισιμότητα</u>''' =====
Το Α είναι το ένα προς ένα αναγώγιμο (ή 1-αναγώγιμο) στο Β αν υπάρχει μια συνολική υπολογίσιμη [[Συνάρτηση|αμφιμονοσήμαντη συνάρτηση]] τέτοια ώστε κάθε n είναι στην Α αν και μόνο αν το f(n) είναι στο Β.
 
===== '''<u>Πολλές προς μία αναγωγισιμότητα</u>''' =====
Αυτό είναι ουσιαστικά η αναγωγή ένα προς ένα χωρίς τον περιορισμό ότι το f είναι αμφιμονοσήμαντο. Το Α είναι πολλοί προς ένα αναγώγιμο (ή m-αναγώγιμη) στο Β, αν υπάρχει μια συνολικά υπολογίσιμη συνάρτηση, έτσι ώστε κάθε n ανήκει στο A αν και μόνο αν το f(n) είναι στο Β.
 
===== '''<u>Αναγωγισιμότητα του Πίνακα Αληθείας</u>''' =====
Το Α είναι αληθινά αναγώγιμο σε πίνακα Β,αν το Α είναι αναγώγιμο κατά Turing στο Β μέσω της μηχανής Turing που υπολογίζει μια συνολική συνάρτηση. Λόγω του συμπαγούς του [[Χώρου Cantor|Cantor χώρου]] , αυτό είναι ισοδύναμο με το να πούμε ότι η μείωση παρουσιάζει έναν ενιαίο κατάλογο ερωτήσεων (εξαρτώμενο μόνο από την είσοδο) στο oracle ταυτόχρονα,και στη συνέχεια, έχοντας δει τις απαντήσεις τους είναι σε θέση να παράγει ένα αποτέλεσμα χωρίς να ζητήσει πρόσθετες ερωτήσεις,ανεξάρτητα με την απάντησης του oracle των αρχικών ερωτημάτων. Πολλές παραλλαγές του πίνακα αληθινής αναγωγής έχουν επίσης μελετηθεί.
 
23

επεξεργασίες

Μενού πλοήγησης