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

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

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

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

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

Ορισμός

Υπολογισιμότητα μίας συνάρτησης είναι μία άτυπη έννοια. Ένας τρόπος να το περιγράψουμε είναι να πούμε ότι μία συνάρτηση είναι υπολογίσιμη αν η τιμή της μπορεί να ληφθεί από μία αποτελεσματική διαδικασία. Με περισσότερη αυστηρότητα, μία συνάρτηση $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ είναι υπολογίσιμη αν και μόνο αν υπάρχει μία αποτελεσματική διαδικασία, τέτοια ώστε δίνοντας κάθε κ-πλειάδα $\mathbf {x}$ των φυσικών αριθμών, θα παράγει την τιμή $f(\mathbf {x} )$ .^[1]^:209 Σε συμφωνία με τον ορισμό αυτό, το υπόλοιπο αυτού του άρθρου υποθέτει ότι οι υπολογίσιμες συναρτήσεις παίρνουν πεπερασμένα πολλούς φυσικούς αριθμούς ως ορίσματα και παράγουν μια τιμή, η οποία είναι ένας φυσικός αριθμός.

Όπως και παραπάνω σε αυτή την άτυπη περιγραφή, υπάρχουν πολλαπλοί επίσημοι, μαθηματικοί ορισμοί. Η κατηγορία των υπολογίσιμων συναρτήσεων μπορεί να οριστεί με πολλά ισοδύναμα μοντέλα υπολογισμού, συμπεριλαμβανομένων

Μηχανές Τούρινγκ
μ-αναδρομικές συναρτήσεις
Λογισμός Λάμδα
Post μηχανές (Ποστ–Τούρινγκ μηχανές και tag μηχανές).
Μηχανές εγγραφής (Tag Μηχανές)

Παρόλο που αυτά τα μοντέλα χρησιμοποιούν διαφορετικές αναπαραστάσεις για τις συναρτήσεις, τις εισόδους και τις εξόδους τους, μεταφράσεις υπάρχουν μεταξύ των δύο μοντέλων, και έτσι κάθε μοντέλο περιγράφει ουσιαστικά το ίδιο σύνολο συναρτήσεων, δίνοντας αφορμή για τη γνώμη ότι η επίσημη υπολογισιμότητα είναι τόσο φυσική και δεν είναι πολύ στενή.^[1]^: 208,262

Για παράδειγμα, κάποιος μπορεί να επισημοποιήσει τις υπολογίσιμες συναρτήσεις ως μ-αναδρομικές συναρτήσεις, οι οποίες είναι μερικές συναρτήσεις που λαμβάνουν πεπερασμένες πλειάδες των φυσικών αριθμών και να επιστρέφουν έναν φυσικό αριθμό (όπως παραπάνω). Είναι η μικρότερη κατηγορία των μερικών συναρτήσεων που περιλαμβάνει τις σταθερές, διαδοχικές και προβεβλημένες συναρτήσεις, και είναι κλειστή κάτω από τη σύνθεση, την πρωτόγονη αναδρομή, και τον μ χειριστή.

Αντίστοιχα, οι υπολογίσιμες συναρτήσεις μπορούν να επισημοποιηθούν ως συναρτήσεις που μπορούν να υπολογιστούν από μία εξειδανικευμένη υπολογιστική μηχανή, όπως μια μηχανή Turing ή μηχανή εγγραφών. Τυπικά μιλώντας, μία μερική συνάρτηση $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ μπορεί να υπολογιστεί, αν και μόνο αν υπάρχει ένα πρόγραμμα υπολογιστή με τις ακόλουθες ιδιότητες:

Αν η $f(\mathbf {x} )$ έχει οριστεί, τότε το πρόγραμμα θα τερματίσει την εισαγωγή $\mathbf {x}$ με την τιμή $f(\mathbf {x} )$ που είναι αποθηκευμένη στη μνήμη του υπολογιστή.
Αν η $f(\mathbf {x} )$ δεν έχει οριστεί, τότε το πρόγραμμα δεν τερματίζει την είσοδο $\mathbf {x}$ .

Χαρακτηριστικά υπολογίσιμων συναρτήσεων

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

Ο Enderton [1977] δίνει τα ακόλουθα χαρακτηριστικά της διαδικασίας για τον υπολογισμό μίας υπολογίσιμης συνάρτησης, παρόμοιοι χαρακτηρισμοί έχουν δοθεί από τους Turing [1936], Rogers [1967], και άλλους.

"Πρέπει να υπάρχουν ακριβείς οδηγίες (δηλαδή το πρόγραμμα), πεπερασμένου μήκους, για τη διαδικασία."

Έτσι κάθε υπολογίσιμη συνάρτηση πρέπει να έχει ένα πεπερασμένο πρόγραμμα το οποίο να περιγράφει ακριβώς το πώς η συνάρτηση είναι να υπολογιστεί. Είναι δυνατόν να υπολογίσουμε τη συνάρτηση μόνο μετά από τις οδηγίες. Εικασίες ή ειδική γνώση δεν είναι απαραίτητα.

"Αν στην διαδικασία δίνεται μια k-πλειάδα x στο πεδίο ορισμό της f και, στη συνέχεια, μετά από ένα πεπερασμένο αριθμό διακριτών βημάτων η διαδικασία πρέπει να τερματίσει και να παράγει f(x)."

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

"Αν στην διαδικασία δοθεί μια k-πλειάδα x η οποία δεν είναι στο πεδίο ορισμού της f, τότε η διαδικασία αυτή μπορεί να συνεχιστεί για πάντα, ποτέ δεν σταματά. Ή μπορεί να κολλήσει σε κάποιο σημείο (δηλαδή, μία εκ των εντολών να μην μπορεί να εκτελεστεί), αλλά δεν πρέπει να προσποιείται ότι παράγει μία τιμή για την f στο x."

Έτσι, αν μία τιμή για το f(x) έχει βρεθεί ποτέ , πρέπει να είναι η σωστή τιμή. Δεν είναι απαραίτητο για τον υπολογιστικό πράκτορα να διακρίνει σωστά αποτελέσματα από τα λανθασμένα, επειδή η διαδικασία είναι πάντα σωστή, όταν παράγει ένα αποτέλεσμα.

Ο Enderton παρακάτω κάνει λίστα αρκετές διευκρινίσεις αυτών των 3 προϋποθέσεων της διαδικασίας για μία υπολογίσιμη συνάρτηση:

Η διαδικασία θα πρέπει θεωρητικά να λειτουργεί για αυθαίρετα μεγάλα ορίσματα. Δεν είναι δεδομένο ότι τα ορίσματα είναι μικρότερα από τον αριθμό των ατόμων στη Γη, για παράδειγμα.
Η διαδικασία απαιτείται να σταματήσει μετά από πεπερασμένα πολλά βήματα για να παράγει ένα αποτέλεσμα, αλλά μπορεί να πάρει αυθαίρετα πολλά βήματα πριν την ανάσχεση. Θεωρείται ότι δεν υπάρχει χρόνος παραγραφής.
Αν και η διαδικασία μπορεί να χρησιμοποιήσει μόνο ένα πεπερασμένο ποσό του χώρου αποθήκευσης κατά τον επιτυχή υπολογισμό, δεν υπάρχει όριο για το ποσό του χώρου που χρησιμοποιείται. Υποθέτουμε ότι επιπλέον αποθηκευτικός χώρος μπορεί να δοθεί στη διαδικασία κάθε φορά που αυτή το ζητάει.

Συνοψίζοντας, με βάση την άποψη αυτή η συνάρτηση είναι υπολογίσιμη αν: (α) δίνεται μια εισαγωγή από το πεδίο ορισμού της, η οποία ενδεχομένως να στηρίζεται στον απεριόριστο αποθηκευτικό χώρο,τότε μπορεί να δώσει την αντίστοιχη έξοδο από την ακόλουθη διαδικασία (πρόγραμμα, αλγόριθμος) που αποτελείται από ένα πεπερασμένο αριθμό από ακριβείς και σαφείς οδηγίες, (β) επιστρέφει μια τέτοια παραγωγή (σταματά) σε ένα πεπερασμένο αριθμό βημάτων, και (γ) αν δοθεί μια εισαγωγή, η οποία δεν είναι στο πεδίο ορισμού της, είτε δεν θα σταματήσει ποτέ ή θα κολλήσει.

Το πεδίο της υπολογιστικής πολυπλοκότητας μελέτα συναρτήσεις με καθορισμένα όρια σχετικά με το χρόνο και/ή τον χώρο που επιτρέπεται σε έναν επιτυχημένο υπολογισμό.

Υπολογίσιμα σύνολα και σχέσεις

Ένα σύνολο $A$ των φυσικών αριθμών λέγεται υπολογίσιμο (συνώνυμα: αναδρομικό, αποφάνσιμο) αν υπάρχει μία υπολογίσιμη, συνολική συνάρτηση $f$ τέτοια ώστε για κάθε φυσικό αριθμό $n$ , να ισχύει $f (n) = 1$ , αν $n$ ανήκει στο Α και $f (n) = 0$ , αν $n$ δεν ανήκει στο Α.

Ένα σύνολο των φυσικών αριθμών ονομάζεται υπολογισίμως αριθμήσιμο (συνώνυμα: αναδρομικά αριθμήσιμο, semidecidable) αν υπάρχει μία υπολογίσιμη συνάρτηση $f$ τέτοια ώστε για κάθε αριθμό $n$ , το $f (n)$ ορίζεται αν και μόνο αν το $n$ ανήκει στο σύνολο. Έτσι, ένα σύνολο είναι υπολογισίμως αριθμήσιμο αν και μόνο αν ανήκει στο πεδίο ορισμού κάποιας υπολογίσιμης συνάρτησης. Η λέξη αριθμήσιμο χρησιμοποιείται γιατί τα ακόλουθα είναι ισοδύναμα για ένα μη-κενό υποσύνολο $B$ των φυσικών αριθμών:

$B$ είναι το πεδίο ορισμού μίας υπολογίσιμης συνάρτησης.
$B$ είναι το εύρος της συνολικής υπολογίσιμης συνάρτησης. Αν το $B$ είναι άπειρο, τότε η συνάρτηση μπορεί να θεωρηθεί ότι είναι ένα προς ένα.

Εάν ένα σύνολο $B$ είναι το εύρος της συνάρτησης $f$ , τότε η συνάρτηση μπορεί να θεωρηθεί ως μια απαρίθμηση του $B$ , επειδή η λίστα $f (0), f (1), ...$ θα περιλαμβάνει κάθε στοιχείο του $B$ .

Επειδή κάθε πεπερασμένη σχέση για τους φυσικούς αριθμούς μπορεί να προσδιοριστεί με ένα αντίστοιχο σύνολο των πεπερασμένων ακολουθιών φυσικών αριθμών, οι έννοιες της υπολογίσιμης συνάρτησης και υπολογισίμως αριθμήσιμης σχέσης μπορούν να οριστούν από τα ανάλογά τους, για τα σύνολα.

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

Στη θεωρία υπολογισιμότητας στην επιστήμη των υπολογιστών, είναι κοινό κάποιος να εξετάσει επίσημες γλώσσες. Ένα αλφάβητο είναι ένα αυθαίρετο σύνολο. Μια λέξη σε ένα αλφάβητο είναι μια πεπερασμένη ακολουθία συμβόλων από το αλφάβητο, το ίδιο σύμβολο μπορεί να χρησιμοποιηθεί περισσότερο από μία φορά. Για παράδειγμα, δυαδικές συμβολοσειρές είναι ακριβώς οι λέξεις του αλφαβήτου ${0, 1}$ . Μια γλώσσα είναι ένα υποσύνολο της συλλογής όλων των λέξεων σε ένα σταθερό αλφάβητο. Για παράδειγμα, η συλλογή όλων των δυαδικών συμβολοσειρών που περιέχουν ακριβώς 3 λέξεις είναι μια γλώσσα πέρα από το δυαδικό αλφάβητο.

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

Μία γλώσσα είναι υπολογισίμως αριθμήσιμη (συνώνυμα: αναδρομικά αριθμήσιμη, semidecidable) αν υπάρχει μία υπολογίσιμη συνάρτηση $f$ τέτοια ώστε το $f (w)$ να ορίζεται αν και μόνο αν η λέξη $w$ ανήκει στη γλώσσα. Ο όρος αριθμήσιμο έχει την ίδια ετυμολογία όπως τα υπολογισίμως αριθμήσιμα σύνολα των φυσικών αριθμών.

Παραδείγματα

Οι ακόλουθες συναρτήσεις είναι υπολογίσιμες:

Κάθε συνάρτηση με πεπερασμένο πεδίο ορισμού, π. χ., κάθε πεπερασμένη ακολουθία των φυσικών αριθμών.
Κάθε συνεχής συνάρτηση f : N^k → N, f(n₁,...n,_k) := n.
Επιπροσθέτως η f : N² → N, f(n₁,n₂) := n₁ + n₂
Η συνάρτηση που δίνει τον κατάλογο πρώτων παραγόντων ενός αριθμού.
Ο μέγιστος κοινός διαιρέτης δύο αριθμών είναι μια υπολογίσιμη συνάρτηση.
Η ταυτότητα του Bézout, μια γραμμική Διοφαντική εξίσωση

Αν οι συναρτήσεις f και g είναι υπολογίσιμες, τότε είναι και οι παρακάτω: f + g, f * g, $f\circ g$ αν η f είναι μοναδιαία, μέγιστο(f,g), ελάχιστο(f,g), πρωτεύον όρισμα μεγίστου{y ≤ f(x)} και πολλοί άλλοι συνδυασμοί.

Τα παρακάτω παραδείγματα δείχνουν ότι μία συνάρτηση μπορεί να είναι υπολογίσιμη, αν και δεν είναι γνωστό ποιος αλγόριθμος την υπολογίζει.

Η συνάρτηση f τέτοια ώστε f(n) = 1, αν υπάρχει μία ακολουθία τουλάχιστον n διαδοχικών πενταριών στην δεκαδική επέκταση του π, και f(n) = 0 διαφορετικά, είναι υπολογίσιμη. (Η συνάρτηση f είναι είτε η σταθερή συνάρτηση 1, η οποία είναι υπολογίσιμη, ή αλλιώς υπάρχει k τέτοιο ώστε f(n) = 1, αν n < k και f(n) = 0, αν n ≥ k. Κάθε τέτοια συνάρτηση είναι υπολογίσιμη. Δεν είναι γνωστό αν υπάρχουν αυθαίρετα μεγάλες διαδρομές των πενταριών στην δεκαδική επέκταση του π, οπότε δεν ξέρουμε ποιες από αυτές τις συναρτήσεις είναι η f. Παρ ' όλα αυτά, γνωρίζουμε ότι η συνάρτηση f , πρέπει να είναι υπολογίσιμη.)
Κάθε πεπερασμένο τμήμα μίας μη-υπολογίσιμης ακολουθίας των φυσικών αριθμών (όπως η συνάρτηση Μπιζι Μπιβερ Σ) είναι υπολογίσιμο. Π.χ., για κάθε φυσικό αριθμό n υπάρχει ένας αλγόριθμος που υπολογίζει την πεπερασμένη ακολουθία Σ(0), Σ(1), Σ(2), ..., Σ(n) — σε αντίθεση με το γεγονός ότι δεν υπάρχει αλγόριθμος που να υπολογίζει το σύνολο της Σ-ακολουθίας, δηλαδή Σ(n) για όλα τα n. Έτσι, "Εκτύπωσε 0, 1, 4, 6, 13" είναι ένα ασήμαντος αλγόριθμος για να υπολογίζει τα Σ(0), Σ(1), Σ(2), Σ(3), Σ(4). Ομοίως, για κάθε δεδομένη τιμή του n, υπάρχει ένας ανάλογος ασήμαντος αλγόριθμος (αν και μπορεί να μην γίνει γνωστό ποτέ ή να μην δημιουργηθεί από κανέναν) για να υπολογίσει τα Σ(0), Σ(1), Σ(2), ..., Σ(n).

Church–Turing διατριβή

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

Πολλά ισοδύναμα μοντέλα υπολογισμού είναι γνωστά, και όλα δίνουν τον ίδιο ορισμό της υπολογίσιμης συνάρτησης (ή ασθενέστερη εκδοχή, σε ορισμένες περιπτώσεις).
Κανένα ισχυρότερο υπολογιστικό μοντέλο το οποίο γενικά θεωρείται να είναι αποτελεσματικά υπολογίσιμο δεν έχει προταθεί.

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

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

Κάθε υπολογίσιμη συνάρτηση έχει μία πεπερασμένη διαδικασία δίνοντας σαφείς, ξεκάθαρες οδηγίες για το πώς να την υπολογίσει. Επιπλέον, αυτή η διαδικασία πρέπει να είναι κωδικοποιημένη στο πεπερασμένο αλφάβητο που χρησιμοποιείται από το υπολογιστικό μοντέλο, υπάρχουν μόνο μετρήσιμα πολλές υπολογίσιμες συναρτήσεις. Για παράδειγμα, οι συναρτήσεις μπορούν να κωδικοποιηθούν χρησιμοποιώντας μια σειρά από bits (το αλφάβητο $Σ = {0, 1}$ ).

Οι πραγματικοί αριθμοί είναι αμέτρητοι οπότε οι περισσότεροι πραγματικοί αριθμοί δεν είναι υπολογίσιμοι. Δείτε υπολογίσιμοι αριθμοί. Το σύνολο των πεπερασμένων συναρτήσεων πάνω στους φυσικούς αριθμούς είναι αμέτρητο, οπότε οι περισσότερες δεν είναι υπολογίσιμες. Συγκεκριμένα παραδείγματα τέτοιων συναρτήσεων είναι η Μπιζι Μπιβερ, η πολυπλοκότητα του Κολμογκόροφ, ή οποιαδήποτε συνάρτηση που εξάγει τα ψηφία ενός μη-υπολογίσιμου αριθμού, όπως η σταθερά του Chaitin.

Ομοίως, τα περισσότερα υποσύνολα των φυσικών αριθμών δεν είναι υπολογίσιμα. Το πρόβλημα τερματισμού ήταν το πρώτο τέτοιο σύνολο για να κατασκευαστεί. Το Αναδρομικό πρόβλημα, που προτείνεται από τον David Hilbert, ρώτησε αν υπάρχει μία αποτελεσματική διαδικασία για να προσδιορίσει ποιες μαθηματικές προτάσεις (που κωδικοποιούνται ως φυσικοί αριθμοί) είναι αληθείς. Ο Τούρινγκ και ο Τσερτς ανεξάρτητα έδειξαν στη δεκαετία του 1930 ότι αυτό το σύνολο των φυσικών αριθμών δεν είναι υπολογίσιμο. Σύμφωνα με την Τσερτς-Τούρινγκ διατριβή, δεν υπάρχει αποτελεσματική διαδικασία (αλγόριθμος) που μπορεί να εκτελέσει αυτούς τους υπολογισμούς.

Επεκτάσεις υπολογισιμότητας

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

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

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

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

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

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

Δείτε επίσης

Αναφορές

↑ ^1,0 ^1,1 Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second έκδοση). USA: Elsevier. ISBN 0-12-238452-0.

Cutland, Νάιτζελ. Υπολογισιμότητα. Cambridge University Press, 1980.
Enderton, H. B. Στοιχεία της αναδρομής θεωρία. Εγχειρίδιο Μαθηματική Λογική (Βόρεια-Ολλανδία 1977), σελ. 527-566.
Rogers, H. Θεωρία αναδρομικών συναρτήσεων και αποτελεσματικού υπολογισμού (McGraw–Hill 1967).
Turing, Α. (1936), Σε Υπολογίσιμους Αριθμούς, Με μια Εφαρμογή στο Entscheidungsproblem. Πρακτικά του Λονδίνου Μαθηματική εταιρεία, Σειρά 2, Τόμος 42 (1936). Reprinted in M. Davis (επιμ.), Το Undecidable, Raven Press, Hewlett, νέα ΥΌΡΚΗ, 1965.

[E02-1] 1,0 ^1,1 Enderton, Herbert (2002). A Mathematical Introduction to Logic (Second έκδοση). USA: Elsevier. ISBN 0-12-238452-0.

[1]