Υπολογίσιμη συνάρτηση

Υπολογίσιμες συναρτήσεις είναι τα βασικά αντικείμενα μελέτης στη θεωρία υπολογισιμότητας. Υπολογίσιμες συναρτήσεις είναι η τυποποιημένη αναλογική της διαισθητικής ιδέας του αλγορίθμου, με την έννοια ότι μια συνάρτηση είναι υπολογίσιμη αν υπάρχει ένας αλγόριθμος που μπορεί να κάνει τη δουλειά της συνάρτησης, δηλαδή με δεδομένο εισόδου το πεδίο ορισμού της συνάρτησης να μπορεί να επιστρέψει το αντίστοιχο της παραγωγής. Υπολογίσιμες συναρτήσεις χρησιμοποιούνται για να συζητήσουν υπολογισιμότητα, χωρίς να αναφέρονται σε κανένα συγκεκριμένο μοντέλο υπολογισμού όπως παραδείγματος χάρη οι μηχανές Τούρινγκ ή οι μηχανές εγγραφών. Κάθε ορισμός, ωστόσο, πρέπει να κάνει αναφορά σε κάποιο συγκεκριμένο μοντέλο υπολογισμού αλλά ισχύουν οι ορισμοί της απόδοσης της ίδιας κατηγορίας των συναρτήσεων.
Συγκεκριμένα μοντέλα υπολογισιμότητας που προκαλούν το σύνολο των υπολογίσιμων συναρτήσεων είναι οι Τούρινγκ-υπολογίσιμες συναρτήσεις και οι μ-αναδρομικές συναρτήσεις.
Πριν τον ακριβή ορισμό της υπολογίσιμης συνάρτησης, οι μαθηματικοί συχνά χρησιμοποιούσαν τον άτυπο όρο αποτελεσματικά υπολογίσιμη. Ο όρος αυτός έχει από τότε να ταυτιστεί με τις υπολογίσιμες συναρτήσεις. Σημειώστε ότι η αποτελεσματική υπολογισιμότητα από αυτές τις συναρτήσεις δεν σημαίνει ότι μπορούν να είναι αποτελεσματικά υπολογίσιμες (δηλαδή υπολογίζεται σε εύλογο χρονικό διάστημα). Στην πραγματικότητα, για κάποιες αποτελεσματικά υπολογίσιμες συναρτήσεις μπορεί να αποδειχθεί ότι κάθε αλγόριθμος που τις υπολογίζει θα είναι πολύ αναποτελεσματικός, με την έννοια ότι ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται εκθετικά (ή ακόμα και υπερεκθετικά) με το μήκος της εισόδου. Τα πεδία της εφικτής υπολογισιμότητας και υπολογιστικής πολυπλοκότητας μελετούν συναρτήσεις που μπορούν να υπολογιστούν αποτελεσματικά.
Σύμφωνα με την Τσερτς–Τούρινγκ διατριβή, υπολογίσιμες συναρτήσεις είναι ακριβώς εκείνες οι συναρτήσεις που μπορούν να υπολογιστούν χρησιμοποιώντας μια συσκευή μηχανικού υπολογισμού με δεδομένο απεριόριστο ποσό χρόνου και χώρου αποθήκευσης. Αντίστοιχα, η διατριβή αυτή ορίζει ότι κάθε συνάρτηση που έχει έναν αλγόριθμο είναι υπολογίσιμη και αντίστροφα. Σημειώστε ότι ένας αλγόριθμος με αυτή την έννοια είναι κατανοητό να είναι μια ακολουθία από βήματα, ένα άτομο με απεριόριστο χρόνο και μια άπειρη προμήθεια από  στυλό και χαρτί θα μπορούσε να συμβαδίσει.
Τα αξιώματα Μπλουμ μπορούν να χρησιμοποιηθούν για να ορίσουμε μια αφηρημένη θεωρία υπολογιστικής πολυπλοκότητας για το σύνολο των υπολογίσιμων συναρτήσεων. Στην θεωρία υπολογιστικής πολυπλοκότητας, το πρόβλημα προσδιορισμού της πολυπλοκότητας μίας υπολογίσιμης συνάρτηση είναι γνωστό ως συναρτησιακό πρόβλημα.

Επίσημες γλώσσες

Στη θεωρία υπολογισιμότητας στην επιστήμη των υπολογιστών, είναι κοινό κάποιος να εξετάσει επίσημες γλώσσες. Ένα αλφάβητο είναι ένα αυθαίρετο σύνολο. Μια λέξη σε ένα αλφάβητο είναι μια πεπερασμένη ακολουθία συμβόλων από το αλφάβητο, το ίδιο σύμβολο μπορεί να χρησιμοποιηθεί περισσότερο από μία φορά. Για παράδειγμα, δυαδικές συμβολοσειρές είναι ακριβώς οι λέξεις του αλφαβήτου {0, 1} . Μια γλώσσα είναι ένα υποσύνολο της συλλογής όλων των λέξεων σε ένα σταθερό αλφάβητο. Για παράδειγμα, η συλλογή όλων των δυαδικών συμβολοσειρών που περιέχουν ακριβώς 3 λέξεις είναι μια γλώσσα πέρα από το δυαδικό αλφάβητο.
Μια βασική ιδιότητα μίας επίσημης γλώσσας είναι το επίπεδο δυσκολίας που απαιτείται για να αποφασιστεί εάν μία συγκεκριμένη λέξη ανήκει στη γλώσσα. Κάποιο σύστημα κωδικοποίησης πρέπει να αναπτυχθεί για να επιτρέψει σε μία υπολογίσιμη συνάρτηση να πάρει μία αυθαίρετη λέξη της γλώσσας ως εισαγωγή. Αυτό συνήθως θεωρείται ρουτίνα. Μία γλώσσα λέγεται υπολογίσιμη (συνώνυμα: αναδρομική, αποφάνσιμη) αν υπάρχει μία υπολογίσιμη συνάρτηση  f  τέτοια ώστε για κάθε λέξη w από το αλφάβητο, ισχύει  f(w) = 1 αν η λέξη ανήκει στη γλώσσα και  f(w) = 0 αν η λέξη δεν ανήκει στη γλώσσα. Έτσι, μία γλώσσα είναι υπολογίσιμη σε περίπτωση που υπάρχει μία διαδικασία που είναι σε θέση να επιβεβαιώσει σωστά αν αυθαίρετες λέξεις ανήκουν στη γλώσσα.
Μία γλώσσα είναι υπολογισίμως αριθμήσιμη (συνώνυμα: αναδρομικά αριθμήσιμη, semidecidable) αν υπάρχει μία υπολογίσιμη συνάρτηση  f  τέτοια ώστε το  f(w) να ορίζεται αν και μόνο αν η λέξη w ανήκει στη γλώσσα. Ο όρος αριθμήσιμο έχει την ίδια ετυμολογία όπως τα υπολογισίμως αριθμήσιμα σύνολα των φυσικών αριθμών.

Μη-υπολογίσιμες συναρτήσεις και άλυτα προβλήματα

Κάθε υπολογίσιμη συνάρτηση έχει μία πεπερασμένη διαδικασία δίνοντας σαφείς, ξεκάθαρες οδηγίες για το πώς να την υπολογίσει. Επιπλέον, αυτή η διαδικασία πρέπει να είναι κωδικοποιημένη στο πεπερασμένο αλφάβητο που χρησιμοποιείται από το υπολογιστικό μοντέλο, υπάρχουν μόνο μετρήσιμα πολλές υπολογίσιμες συναρτήσεις. Για παράδειγμα, οι συναρτήσεις μπορούν να κωδικοποιηθούν χρησιμοποιώντας μια σειρά από bits (το αλφάβητο Σ = {0, 1} ).
Οι πραγματικοί αριθμοί είναι αμέτρητοι οπότε οι περισσότεροι πραγματικοί αριθμοί δεν είναι υπολογίσιμοι. Δείτε υπολογίσιμοι αριθμοί. Το σύνολο των πεπερασμένων συναρτήσεων πάνω στους φυσικούς αριθμούς είναι αμέτρητο, οπότε οι περισσότερες δεν είναι υπολογίσιμες. Συγκεκριμένα παραδείγματα τέτοιων συναρτήσεων είναι η Μπιζι Μπιβερ, η πολυπλοκότητα του Κολμογκόροφ, ή οποιαδήποτε συνάρτηση που εξάγει τα ψηφία ενός μη-υπολογίσιμου αριθμού, όπως η σταθερά του Chaitin.
Ομοίως, τα περισσότερα υποσύνολα των φυσικών αριθμών δεν είναι υπολογίσιμα. Το πρόβλημα τερματισμού ήταν το πρώτο τέτοιο σύνολο για να κατασκευαστεί. Το Αναδρομικό πρόβλημα, που προτείνεται από τον David Hilbert, ρώτησε αν υπάρχει μία αποτελεσματική διαδικασία για να προσδιορίσει ποιες μαθηματικές προτάσεις (που κωδικοποιούνται ως φυσικοί αριθμοί) είναι αληθείς. Ο Τούρινγκ και ο Τσερτς ανεξάρτητα έδειξαν στη δεκαετία του 1930 ότι αυτό το σύνολο των φυσικών αριθμών δεν είναι υπολογίσιμο. Σύμφωνα με την Τσερτς-Τούρινγκ διατριβή, δεν υπάρχει αποτελεσματική διαδικασία (αλγόριθμος) που μπορεί να εκτελέσει αυτούς τους υπολογισμούς.

Σχετική υπολογισιμότητα

Η έννοια της υπολογισιμότητας μίας συνάρτησης μπορεί να σχετικοποιείται σε ένα αυθαίρετο σύνολο των φυσικών αριθμών Α. Μια συνάρτηση f ορίζεται να είναι υπολογίσιμη στο Α (αντίστοιχα Α-υπολογίσιμη ή υπολογίσιμη σε σχέση με Α) όταν πληροί τον ορισμό μίας υπολογίσιμης συνάρτησης με τις τροποποιήσεις που επιτρέπουν την πρόσβαση στο Α ως μαντείο. Όπως και με την έννοιά της,για  μία υπολογίσιμη συνάρτηση σχετικής υπολογισιμότητας μπορούν να δοθούν ισοδύναμοι ορισμοί σε πολλά διαφορετικά μοντέλα υπολογισμού. Αυτό συνήθως επιτυγχάνεται συμπληρώνοντας το μοντέλο υπολογισμού με μία επιπλέον πρωτόγονη λειτουργία η οποία σας ρωτά εάν ένας δεδομένος ακέραιος είναι μέλος του Α. Μπορούμε επίσης να μιλήσουμε για το αν η f είναι υπολογίσιμη στη g , εντοπίζοντας την g με το γράφημά της.

Υψηλότερη θεωρία αναδρομής

Η υπεραριθμητική θεωρία μελετά τα σύνολα που μπορούν να υπολογιστούν από έναν υπολογίσιμο αύξων αριθμό που επαναλαμβάνεται από τον Turing άλμα του στο κενό σύνολο. Αυτό είναι ισοδύναμο με σύνολα που ορίζονται τόσο από την καθολική και την υπαρξιακή φόρμουλα στη γλώσσα της δεύτερης τάξης αριθμητικής και σε ορισμένα μοντέλα της Hypercomputation. Ακόμα πιο γενικές αναδρομικές θεωρίες έχουν μελετηθεί, όπως η E-αναδρομή θεωρία κατά την οποία κάθε σύνολο μπορεί να χρησιμοποιηθεί ως επιχείρημα σε μία E-αναδρομική συνάρτηση.

Υπέρ-υπολογισμός

Αν και η Τσερτς-Τούρινγκ διατριβή αναφέρει ότι οι υπολογίσιμες συναρτήσεις περιλαμβάνουν όλες τις συναρτήσεις με αλγορίθμους, είναι δυνατό να λαμβάνονται υπόψη ευρύτερες κατηγορίες συναρτήσεων που χαλαρώνουν οι απαιτήσεις που οι αλγόριθμοι πρέπει να κατέχουν. Το πεδίο της Hypercomputation μελετά μοντέλα υπολογισμού που υπερβαίνουν τους φυσιολογικούς Turing υπολογισμούς.