Βικιπαίδεια

Υπολογίσιμη συνάρτηση: Διαφορά μεταξύ των αναθεωρήσεων

Περιήγηση ιστορικού διαδραστικά
← Προηγούμενη διαφοράΕπόμενη διαφορά →
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
ΟπτικήΚώδικας wiki
TalibNB (συζήτηση | συνεισφορές)
66 επεξεργασίες
Τυπογραφικό
Ετικέτες: Επεξεργασία από κινητό Διαδικτυακή επεξεργασία από κινητό
TalibNB (συζήτηση | συνεισφορές)
66 επεξεργασίες
μ Τυπογραφικό
Γραμμή 13:
 
Όπως και παραπάνω σε αυτή την άτυπη περιγραφή, υπάρχουν πολλαπλοί επίσημοι, μαθηματικοί ορισμοί. Η κατηγορία των υπολογίσιμων συναρτήσεων μπορεί να οριστεί με πολλά ισοδύναμα [[Mοντέλο υπολογισμού|μοντέλα υπολογισμού]], συμπεριλαμβανομένων
* '''[[Μηχανή ΤιούρινγκΤούρινγκ|Μηχανές ΤιούρινγκΤούρινγκ]]'''
* '''[[Μ-αναδρομική συνάρτηση|μ-αναδρομικές συναρτήσεις]]'''
* '''[[Λογισμός λάμδα|Λογισμός Λάμδα]]'''
* '''Post μηχανές''' ([[Ποστ–ΤιούρινγκΠοστ–Τούρινγκ μηχανή|Ποστ–ΤιούρινγκΠοστ–Τούρινγκ μηχανές]] και [[Σύστημα εγγραφής|tag μηχανές]]).
* '''[[Μηχανή εγγραφής|Μηχανές εγγραφής]] (Tag Μηχανές)'''
Παρόλο που αυτά τα μοντέλα χρησιμοποιούν διαφορετικές αναπαραστάσεις για τις συναρτήσεις, τις εισόδους και τις εξόδους τους, μεταφράσεις υπάρχουν μεταξύ των δύο μοντέλων, και έτσι κάθε μοντέλο περιγράφει ουσιαστικά το ίδιο σύνολο συναρτήσεων, δίνοντας αφορμή για τη γνώμη ότι η επίσημη υπολογισιμότητα είναι τόσο φυσική και δεν είναι πολύ στενή.<ref>{{Cite book|title=A Mathematical Introduction to Logic|last=Herbert|first=Enderton|publisher=|year=2002|isbn=0-12-238452-0.|location=USA: Elsevier|page=208,262}}</ref>
Γραμμή 22:
Για παράδειγμα, κάποιος μπορεί να επισημοποιήσει τις υπολογίσιμες συναρτήσεις ως [[Μ-αναδρομική συνάρτηση|μ-αναδρομικές συναρτήσεις]], οι οποίες είναι [[Μερική συνάρτηση|μερικές συναρτήσεις]] που λαμβάνουν πεπερασμένες πλειάδες των [[Φυσικός αριθμός|φυσικών αριθμών]] και να επιστρέφουν έναν φυσικό αριθμό (όπως παραπάνω). Είναι η μικρότερη κατηγορία των μερικών συναρτήσεων που περιλαμβάνει τις σταθερές, διαδοχικές και προβεβλημένες συναρτήσεις, και είναι κλειστή κάτω από τη [[Σύνθεση συνάρτησης|σύνθεση]], την [[Πρωτόγονη αναδρομική συνάρτηση|πρωτόγονη αναδρομή]], και τον [[μ χειριστή]].
 
Αντίστοιχα, οι υπολογίσιμες συναρτήσεις μπορούν να επισημοποιηθούν ως συναρτήσεις που μπορούν να υπολογιστούν από μία εξειδανικευμένη υπολογιστική μηχανή, όπως μια [[Μηχανή ΤιούρινγκΤούρινγκ|μηχανή Turing]] ή [[Μηχανή εγγραφής|μηχανή εγγραφών]]. Τυπικά μιλώντας, μία [[μερική συνάρτηση]] <math>f:\mathbb N^k\rightarrow\mathbb N</math> μπορεί να υπολογιστεί, αν και μόνο αν υπάρχει ένα πρόγραμμα υπολογιστή με τις ακόλουθες ιδιότητες:
# Αν η <math>f(\mathbf x)</math> έχει οριστεί, τότε το πρόγραμμα θα τερματίσει την εισαγωγή <math>\mathbf x</math> με την τιμή <math>f(\mathbf x)</math> που είναι αποθηκευμένη στη μνήμη του υπολογιστή.
# Αν η <math>f(\mathbf x)</math> δεν έχει οριστεί, τότε το πρόγραμμα δεν τερματίζει την είσοδο <math>\mathbf x</math>.
Γραμμή 78:
 
== Church–Turing διατριβή ==
H '''Τσερτς-ΤιούρινγκΤούρινγκ διατριβή''' αναφέρει ότι οποιαδήποτε συνάρτηση υπολογισμένη από μία διαδικασία που κατέχει τις τρεις ιδιότητες που αναφέρονται [[:en:Computable_function#Characteristics_of_computable_functions|παραπάνω]] είναι μία υπολογίσιμη συνάρτηση. Επειδή αυτές οι τρεις ιδιότητες δεν αναφέρονται επίσημα, η Τσερτς-ΤιούρινγκΤούρινγκ διατριβή δεν μπορεί να αποδειχθεί. Τα ακόλουθα στοιχεία όμως λαμβάνονται συχνά ως αποδεικτικά στοιχεία για τη διατριβή:
* Πολλά ισοδύναμα μοντέλα υπολογισμού είναι γνωστά, και όλα δίνουν τον ίδιο ορισμό της υπολογίσιμης συνάρτησης (ή ασθενέστερη εκδοχή, σε ορισμένες περιπτώσεις).
* Κανένα ισχυρότερο υπολογιστικό μοντέλο το οποίο γενικά θεωρείται να είναι [[Αποτελεσματική μέθοδος|αποτελεσματικά υπολογίσιμο]] δεν έχει προταθεί.
Η Τσερτς-ΤιούρινγκΤούρινγκ διατριβή μερικές φορές χρησιμοποιείται σε αποδείξεις για να δικαιολογήσει ότι μία συγκεκριμένη συνάρτηση είναι υπολογίσιμη, δίνοντας μία συγκεκριμένη περιγραφή της διαδικασίας για τον υπολογισμό. Αυτό επιτρέπεται διότι πιστεύεται ότι όλες αυτές οι χρήσεις της διατριβής μπορούν να αφαιρεθούν μέσα από την κουραστική διαδικασία της γραφής μίας επίσημης διαδικασίας για τη συνάρτηση σε κάποιο μοντέλο υπολογισμού.
 
== Μη-υπολογίσιμες συναρτήσεις και άλυτα προβλήματα ==
Γραμμή 88:
Οι πραγματικοί αριθμοί είναι αμέτρητοι οπότε οι περισσότεροι πραγματικοί αριθμοί δεν είναι υπολογίσιμοι. Δείτε [[Υπολογίσιμος αριθμός|υπολογίσιμοι αριθμοί]]. Το σύνολο των [[Πεπερασμένο|πεπερασμένων]] συναρτήσεων πάνω στους φυσικούς αριθμούς είναι αμέτρητο, οπότε οι περισσότερες δεν είναι υπολογίσιμες. Συγκεκριμένα παραδείγματα τέτοιων συναρτήσεων είναι η [[συνάρτηση Busy Beaver|Μπιζι Μπιβερ]], η [[πολυπλοκότητα του Kolmogorov|πολυπλοκότητα του Κολμογκόροφ]], ή οποιαδήποτε συνάρτηση που εξάγει τα ψηφία ενός μη-υπολογίσιμου αριθμού, όπως η [[σταθερά του Chaitin]].
 
Ομοίως, τα περισσότερα υποσύνολα των φυσικών αριθμών δεν είναι υπολογίσιμα. Το [[πρόβλημα τερματισμού]] ήταν το πρώτο τέτοιο σύνολο για να κατασκευαστεί. Το [[Αναδρομικό πρόβλημα]], που προτείνεται από τον [[Ντάβιντ Χίλμπερτ|David Hilbert]], ρώτησε αν υπάρχει μία αποτελεσματική διαδικασία για να προσδιορίσει ποιες μαθηματικές προτάσεις (που κωδικοποιούνται ως φυσικοί αριθμοί) είναι αληθείς. Ο ΤιούρινγκΤούρινγκ και ο Τσερτς ανεξάρτητα έδειξαν στη δεκαετία του 1930 ότι αυτό το σύνολο των φυσικών αριθμών δεν είναι υπολογίσιμο. Σύμφωνα με την Τσερτς-ΤιούρινγκΤούρινγκ διατριβή, δεν υπάρχει αποτελεσματική διαδικασία (αλγόριθμος) που μπορεί να εκτελέσει αυτούς τους υπολογισμούς.
 
== Επεκτάσεις υπολογισιμότητας ==
Γραμμή 99:
 
=== Υπέρ-υπολογισμός ===
Αν και η Τσερτς-ΤιούρινγκΤούρινγκ διατριβή αναφέρει ότι οι υπολογίσιμες συναρτήσεις περιλαμβάνουν όλες τις συναρτήσεις με αλγορίθμους, είναι δυνατό να λαμβάνονται υπόψη ευρύτερες κατηγορίες συναρτήσεων που χαλαρώνουν οι απαιτήσεις που οι αλγόριθμοι πρέπει να κατέχουν. Το πεδίο της Hypercomputation μελετά μοντέλα υπολογισμού που υπερβαίνουν τους φυσιολογικούς Turing υπολογισμούς.
 
== Δείτε επίσης ==
Γραμμή 106:
* [[Θεωρία υπολογισμού]]
* Θεωρία της [[Θεωρία υπολογισιμότητας|Αναδρομή]]<nowiki/>ς
* [[Βαθμός Turing|Βαθμός ΤιούρινγκΤούρινγκ]]
* [[Αριθμητική ιεραρχία]]
* [[Υπερ-υπολογισμός]]
Γραμμή 117:
* [[Χέρμπερντ Έντερτον|Enderton]], H. B. Στοιχεία της αναδρομής θεωρία. ''Εγχειρίδιο Μαθηματική Λογική'' (Βόρεια-Ολλανδία 1977), σελ.&#x20;527-566.
* Rogers, H. ''Θεωρία αναδρομικών συναρτήσεων και αποτελεσματικού υπολογισμού'' (McGraw–Hill 1967).
* [[Άλαν ΤιούρινγκΤούρινγκ|Turing, Α.]] (1936), Σε Υπολογίσιμους Αριθμούς, Με μια Εφαρμογή στο Entscheidungsproblem. ''Πρακτικά του Λονδίνου Μαθηματική εταιρεία'', Σειρά 2, Τόμος 42 (1936). Reprinted in M. Davis (επιμ.), ''Το Undecidable'', Raven Press, Hewlett, νέα ΥΌΡΚΗ, 1965.
[[Κατηγορία:Θεωρία υπολογισμού]]
Ανακτήθηκε από "https://el.wikipedia.org/wiki/Υπολογίσιμη_συνάρτηση"