Αποτελεσματική μέθοδος
Στη λογική, τα μαθηματικά και την επιστήμη των υπολογιστών, ειδικά περαιτέρω θεωρία της λογικής και θεωρία υπολογισιμότητας, μια αποτελεσματική μέθοδος[1] ή αποτελεσματική διαδικασία είναι μια διαδικασία για την επίλυση ενός προβλήματος από μια συγκεκριμένη κατηγορία. Μια αποτελεσματική μέθοδος μερικές φορές ονομάζεται επίσης μηχανική μέθοδος ή διαδικασία.[2]
Ορισμός[Επεξεργασία | επεξεργασία κώδικα]
Ο ορισμός της μίας αποτελεσματικής μεθόδου περιλαμβάνει περισσότερα από ότι η ίδια η μέθοδος. Προκειμένου μια μέθοδος να ονομάζεται αποτελεσματική, πρέπει να αντιμετωπίζεται με σεβασμό σε μία κλάση προβλημάτων. Εξαιτίας αυτού, η μέθοδος μπορεί να είναι αποτελεσματική ως προς μία κλάση προβλημάτων και αναποτελεσματική, με σεβασμό σε μια διαφορετική κλάση.
Μια μέθοδος επίσημα ονομάζεται αποτελεσματική για μία κλάση προβλημάτων όταν πληροί τα εξής κριτήρια:
- Αποτελείται από ένα πεπερασμένο αριθμό με ακριβείς, πεπερασμένες οδηγίες.
- Όταν εφαρμόζεται σε ένα πρόβλημα από την κλάση:
- Πάντα τελειώνει (τερματίζει) μετά από ένα πεπερασμένο αριθμό βημάτων.
- Πάντα παράγει μια σωστή απάντηση.
- Στην αρχή, αυτό μπορεί να γίνει από έναν άνθρωπο, χωρίς βοηθήματα, εκτός από υλικά γραφής.
- Οι οδηγίες πρέπει μόνο να ακολουθούνται αυστηρά για να πετύχει. Με άλλα λόγια, δεν απαιτείται εφευρετικότητα για να πετύχει.[3]
Προαιρετικά, μπορεί να απαιτηθεί, επίσης, ότι η μέθοδος δεν θα επιστρέφει αποτέλεσμα όπως σαν να ήταν μια απάντηση όταν η μέθοδος εφαρμόζεται σε ένα πρόβλημα έξω από την κλάση. Προσθέτοντας αυτή την απαίτηση μειώνεται το σύνολο των κλάσεων για τις οποίες δεν είναι αποτελεσματική μέθοδος.
Αλγόριθμοι[Επεξεργασία | επεξεργασία κώδικα]
Μια αποτελεσματική μέθοδος για τον υπολογισμό των τιμών της συνάρτησης είναι ένας αλγόριθμος. Συναρτήσεις για τις οποίες υπάρχει μερικές φορές μια αποτελεσματική μέθοδος ονομάζεται αποτελεσματικά υπολογίσιμη.
Υπολογίσιμες συναρτήσεις[Επεξεργασία | επεξεργασία κώδικα]
Αρκετές ανεξάρτητες προσπάθειες για να δώσουν έναν επίσημο χαρακτηρισμό μίας αποτελεσματικής υπολογισιμότητας οδήγησαν σε μια ποικιλία προτεινόμενων ορισμών (γενική αναδρομή, μηχανές Turing, λ-λογισμός) που αργότερα φάνηκε να είναι ισοδύναμες. Η έννοια που συλλήφθηκε από αυτούς τους ορισμούς είναι γνωστή ως περιοδικότητα ή αποτελεσματική υπολογισιμότητα.
Η Church-Turing διατριβή αναφέρει ότι οι δύο έννοιες συμπίπτουν, κάθε αριθμός-θεωρητική συνάρτηση που να είναι αποτελεσματικά υπολογίσιμη, μπορεί να υπολογιστεί ότι είναι αναδρομικά υπολογίσιμη. Καθώς αυτό δεν είναι μια μαθηματική δήλωση, δεν μπορεί να αποδειχθεί με μαθηματική απόδειξη.
Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]
- Αποφανσιμότητα (λογική)
- Πρόβλημα απόφασης
- Συναρτησιακό πρόβλημα
- Αποτελεσματικά συμπεράσματα στην θεωρία αριθμών
- Αναδρομικό σύνολο
- Αναποφάσιστο πρόβλημα
References[Επεξεργασία | επεξεργασία κώδικα]
- ↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
- ↑ Copeland, B.J.· Copeland, Jack· Proudfoot, Diane (Ιουνίου 2000). «The Turing-Church Thesis». AlanTuring.net. Turing Archive for the History of Computing. Ανακτήθηκε στις 23 Μαρτίου 2013.
- ↑ The Cambridge Dictionary of Philosophy, effective procedure
- S. C. Kleene (1967), Μαθηματική λογική. Ανατύπωση, Dover, 2002, ISBN 0-486-42533-9, pp. 233 επ. esp. σ. 231.
|
Αυτή η λογική που σχετίζεται με το άρθρο αυτό είναι ένα απόκομμα. Μπορείτε να βοηθήσετε την Βικιπαίδεια από την επέκταση. |