Υπολογίσιμη συνάρτηση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Αντικατάσταση παρωχημένου προτύπου με references tag |
Τυπογραφικό Ετικέτες: Επεξεργασία από κινητό Διαδικτυακή επεξεργασία από κινητό |
||
Γραμμή 1:
'''Υπολογίσιμες συναρτήσεις''' είναι τα βασικά αντικείμενα μελέτης στη [[θεωρία υπολογισιμότητας]]. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του [[Αλγόριθμος|αλγορίθμου]], με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο [[Mοντέλο υπολογισμού|μοντέλο υπολογισμού]] όπως παραδείγματος χάρη οι [[Μηχανή
Συγκεκριμένα μοντέλα υπολογισιμότητας που προκαλούν το σύνολο των υπολογίσιμων συναρτήσεων είναι οι [[Μηχανή
Πριν τον ακριβή ορισμό της υπολογίσιμης συνάρτησης, [[Μαθηματικός|οι μαθηματικοί]] συχνά χρησιμοποιούσαν τον άτυπο όρο ''αποτελεσματικά υπολογίσιμη''. Ο όρος αυτός έχει από τότε να ταυτιστεί με τις υπολογίσιμες συναρτήσεις. Σημειώστε ότι η αποτελεσματική υπολογισιμότητα από αυτές τις συναρτήσεις δεν σημαίνει ότι μπορούν να είναι ''αποτελεσματικά'' υπολογίσιμες (δηλαδή υπολογίζεται σε εύλογο χρονικό διάστημα). Στην πραγματικότητα, για κάποιες αποτελεσματικά υπολογίσιμες συναρτήσεις μπορεί να αποδειχθεί ότι κάθε αλγόριθμος που τις υπολογίζει θα είναι πολύ αναποτελεσματικός, με την έννοια ότι ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται [[Εκθετική αύξηση|εκθετικά]] (ή ακόμα και [[υπερεκθετικά]]) με το μήκος της εισόδου. Τα πεδία της[[Θεωρία πολυπλοκότητας| εφικτής υπολογισιμότητας]] και [[Θεωρία πολυπλοκότητας|υπολογιστικής πολυπλοκότητας]] μελετούν συναρτήσεις που μπορούν να υπολογιστούν αποτελεσματικά.
Σύμφωνα με την [[Church–Turing διατριβή|Τσερτς–]][[Μηχανή
Τα [[αξιώματα Μπλουμ]] μπορούν να χρησιμοποιηθούν για να ορίσουμε μια αφηρημένη [[Θεωρία πολυπλοκότητας|θεωρία υπολογιστικής πολυπλοκότητας]] για το σύνολο των υπολογίσιμων συναρτήσεων. Στην θεωρία υπολογιστικής πολυπλοκότητας, το πρόβλημα προσδιορισμού της πολυπλοκότητας μίας υπολογίσιμης συνάρτηση είναι γνωστό ως [[Συναρτησιακό πρόβλημ|συναρτησιακό πρόβλημα]].
| |||