Η διατριβή Church-Turing αναφέρεται στην έννοια μιας αποτελεσματικής, συστηματικής ή μηχανικής μεθόδου στη λογική, τα μαθηματικά και την επιστήμη των υπολογιστών. Διατυπώνεται ως περιγραφή της διαισθητικής έννοιας της υπολογισιμότητας και, σε σχέση με τις γενικές αναδρομικές συναρτήσεις, ονομάζεται συχνότερα διατριβή του Church. Αναφέρεται επίσης στη θεωρία των υπολογιστικών συναρτήσεων. Η διατριβή εμφανίστηκε τη δεκαετία του 1930, όταν οι ίδιοι οι υπολογιστές δεν υπήρχαν ακόμη. Αργότερα πήρε το όνομά του από τον Αμερικανό μαθηματικό Alonso Church και τον Βρετανό συνάδελφό του Alan Turing.
Αποτελεσματικότητα της μεθόδου για την επίτευξη του αποτελέσματος
Η πρώτη συσκευή που έμοιαζε με σύγχρονο υπολογιστή ήταν το Bombie, μια μηχανή που δημιουργήθηκε από τον Άγγλο μαθηματικό Άλαν Τούρινγκ. Χρησιμοποιήθηκε για την αποκρυπτογράφηση γερμανικών μηνυμάτων κατά τον Β' Παγκόσμιο Πόλεμο. Αλλά για τη διατριβή του και την επισημοποίηση της έννοιας ενός αλγορίθμου, χρησιμοποίησε αφηρημένες μηχανές, που αργότερα ονομάστηκαν μηχανές Turing. Η διατριβή παρουσιάζειενδιαφέρον τόσο για μαθηματικούς όσο και για προγραμματιστές, αφού αυτή η ιδέα ενέπνευσε τους δημιουργούς των πρώτων υπολογιστών.
Στη θεωρία υπολογισιμότητας, η διατριβή Church-Turing είναι επίσης γνωστή ως η εικασία σχετικά με τη φύση των υπολογίσιμων συναρτήσεων. Δηλώνει ότι για οποιαδήποτε αλγοριθμικά υπολογίσιμη συνάρτηση σε φυσικούς αριθμούς, υπάρχει μια μηχανή Turing ικανή να την υπολογίσει. Ή, με άλλα λόγια, υπάρχει ένας αλγόριθμος κατάλληλος για αυτό. Ένα πολύ γνωστό παράδειγμα της αποτελεσματικότητας αυτής της μεθόδου είναι το τεστ του πίνακα αληθείας για τον έλεγχο ταυτολογίας.
Ένας τρόπος για να επιτευχθεί οποιοδήποτε επιθυμητό αποτέλεσμα ονομάζεται "αποτελεσματικός", "συστηματικός" ή "μηχανικός" εάν:
- Η μέθοδος προσδιορίζεται με όρους πεπερασμένου αριθμού ακριβών εντολών, κάθε εντολή εκφράζεται χρησιμοποιώντας έναν πεπερασμένο αριθμό χαρακτήρων.
- Θα εκτελεστεί χωρίς σφάλματα, θα παράγει το επιθυμητό αποτέλεσμα σε έναν συγκεκριμένο αριθμό βημάτων.
- Η μέθοδος μπορεί να πραγματοποιηθεί από άνθρωπο χωρίς βοήθεια με οποιονδήποτε εξοπλισμό εκτός από χαρτί και μολύβι
- Δεν απαιτεί κατανόηση, διαίσθηση ή εφευρετικότητα από την πλευρά του ατόμου που εκτελεί την ενέργεια
Νωρίτερα στα μαθηματικά, ο άτυπος όρος "αποτελεσματικά υπολογίσιμος" χρησιμοποιήθηκε για να αναφέρεται σε συναρτήσεις που μπορούν να υπολογιστούν με μολύβι και χαρτί. Αλλά η ίδια η έννοια της αλγοριθμικής υπολογισιμότητας ήταν πιο διαισθητική από οτιδήποτε συγκεκριμένο. Τώρα χαρακτηρίστηκε από μια συνάρτηση με φυσικό όρισμα, για την οποία υπάρχει αλγόριθμος υπολογισμού. Ένα από τα επιτεύγματα του Άλαν Τούρινγκ ήταναναπαράσταση ενός τυπικά ακριβούς κατηγορήματος, με τη βοήθεια του οποίου θα ήταν δυνατή η αντικατάσταση του άτυπου, εάν χρησιμοποιηθεί η συνθήκη αποτελεσματικότητας της μεθόδου. Η Εκκλησία έκανε την ίδια ανακάλυψη.
Βασικές έννοιες αναδρομικών συναρτήσεων
Η αλλαγή των κατηγορημάτων του Turing, με την πρώτη ματιά, φαινόταν διαφορετική από αυτή που πρότεινε ο συνάδελφός του. Αλλά ως αποτέλεσμα, αποδείχθηκαν ισοδύναμα, με την έννοια ότι καθένα από αυτά επιλέγει το ίδιο σύνολο μαθηματικών συναρτήσεων. Η διατριβή Church-Turing είναι ο ισχυρισμός ότι αυτό το σύνολο περιέχει κάθε συνάρτηση της οποίας οι τιμές μπορούν να ληφθούν με μια μέθοδο που ικανοποιεί τις συνθήκες απόδοσης. Υπήρχε μια άλλη διαφορά μεταξύ των δύο ανακαλύψεων. Ήταν ότι ο Τσερτ εξέτασε μόνο παραδείγματα θετικών ακεραίων, ενώ ο Τούρινγκ περιέγραψε το έργο του ότι κάλυπτε υπολογιστικές συναρτήσεις με μια αναπόσπαστη ή πραγματική μεταβλητή.
Κοινές αναδρομικές συναρτήσεις
Η αρχική διατύπωση της Εκκλησίας δηλώνει ότι ο υπολογισμός μπορεί να γίνει χρησιμοποιώντας τον λ-λογισμό. Αυτό ισοδυναμεί με τη χρήση γενικών αναδρομικών συναρτήσεων. Η διατριβή Church-Turing καλύπτει περισσότερα είδη υπολογισμών από ό,τι είχε αρχικά θεωρηθεί. Για παράδειγμα, σχετίζονται με κυψελωτά αυτόματα, συνδυαστές, μηχανές καταγραφής και συστήματα υποκατάστασης. Το 1933, οι μαθηματικοί Kurt Gödel και Jacques Herbrand δημιούργησαν έναν επίσημο ορισμό μιας τάξης που ονομάζεται γενικές αναδρομικές συναρτήσεις. Χρησιμοποιεί συναρτήσεις όπου είναι δυνατά περισσότερα από ένα επιχειρήματα.
Δημιουργία μεθόδουλ-λογισμός
Το 1936, η Alonso Church δημιούργησε μια μέθοδο προσδιορισμού που ονομάζεται λ-λογισμός. Συνδέθηκε με φυσικούς αριθμούς. Μέσα στον λ-λογισμό, ο επιστήμονας προσδιόρισε την κωδικοποίησή τους. Ως αποτέλεσμα, ονομάζονται αριθμοί Εκκλησίας. Μια συνάρτηση που βασίζεται σε φυσικούς αριθμούς ονομαζόταν λ-υπολογίσιμη. Υπήρχε ένας άλλος ορισμός. Η συνάρτηση από τη διατριβή του Church ονομάζεται λ-υπολογίσιμη υπό δύο συνθήκες. Η πρώτη ακουγόταν ως εξής: αν υπολογιζόταν σε στοιχεία της Εκκλησίας, και η δεύτερη προϋπόθεση ήταν η δυνατότητα να αντιπροσωπεύεται από ένα μέλος του λ-λογισμού.
Επίσης το 1936, προτού μελετήσει το έργο του συναδέλφου του, ο Turing δημιούργησε ένα θεωρητικό μοντέλο για τις αφηρημένες μηχανές που τώρα ονομάζονται από αυτόν. Θα μπορούσαν να κάνουν υπολογισμούς χειραγωγώντας τους χαρακτήρες στην κασέτα. Αυτό ισχύει και για άλλες μαθηματικές δραστηριότητες που βρίσκονται στη θεωρητική επιστήμη των υπολογιστών, όπως ο κβαντικός υπολογισμός πιθανοτήτων. Η λειτουργία από τη διατριβή του Church τεκμηριώθηκε μόνο αργότερα χρησιμοποιώντας μια μηχανή Turing. Αρχικά, βασίστηκαν στον λ-λογισμό.
Υπολογισιμότητα συναρτήσεων
Όταν οι φυσικοί αριθμοί κωδικοποιούνται κατάλληλα ως ακολουθίες χαρακτήρων, μια συνάρτηση σε φυσικούς αριθμούς λέγεται ότι μπορεί να υπολογιστεί με Turing, εάν η αφηρημένη μηχανή βρήκε τον απαιτούμενο αλγόριθμο και εκτύπωσε αυτήν τη συνάρτηση σε ταινία. Μια τέτοια συσκευή, που δεν υπήρχε στη δεκαετία του 1930, θα θεωρούνταν στο μέλλον υπολογιστής. Η αφηρημένη μηχανή Turing και η διατριβή του Church προανήγγειλαν μια εποχή ανάπτυξηςυπολογιστικές συσκευές. Αποδείχθηκε ότι οι κατηγορίες συναρτήσεων που ορίστηκαν επίσημα και από τους δύο επιστήμονες συμπίπτουν. Ως εκ τούτου, ως αποτέλεσμα, και οι δύο δηλώσεις συνδυάστηκαν σε μία. Οι υπολογιστικές συναρτήσεις και η διατριβή του Church είχαν επίσης ισχυρή επίδραση στην έννοια της υπολογισιμότητας. Έγιναν επίσης ένα σημαντικό εργαλείο για τη μαθηματική λογική και τη θεωρία αποδείξεων.
Αιτιολόγηση και προβλήματα της μεθόδου
Υπάρχουν αντικρουόμενες απόψεις σχετικά με τη διατριβή. Πολλά στοιχεία συλλέχθηκαν για την «υπόθεση εργασίας» που προτάθηκε από τους Church και Turing το 1936. Αλλά όλες οι γνωστές μέθοδοι ή λειτουργίες για την ανακάλυψη νέων αποτελεσματικά υπολογίσιμων συναρτήσεων από δεδομένες συνδέονταν με μεθόδους κατασκευής μηχανών, οι οποίες δεν υπήρχαν τότε. Για να αποδείξουμε τη θέση Church-Turing, ξεκινάμε από το γεγονός ότι κάθε ρεαλιστικό μοντέλο υπολογισμού είναι ισοδύναμο.
Λόγω της ποικιλίας των διαφορετικών αναλύσεων, αυτό θεωρείται γενικά ως ιδιαίτερα ισχυρή απόδειξη. Όλες οι προσπάθειες για τον ακριβέστερο ορισμό της διαισθητικής έννοιας μιας αποτελεσματικά υπολογίσιμης συνάρτησης αποδείχθηκαν ισοδύναμες. Κάθε ανάλυση που έχει προταθεί έχει αποδειχθεί ότι ξεχωρίζει την ίδια κατηγορία συναρτήσεων, δηλαδή αυτές που είναι υπολογίσιμες από μηχανές Turing. Ωστόσο, ορισμένα υπολογιστικά μοντέλα αποδείχθηκαν πιο αποτελεσματικά όσον αφορά τη χρήση χρόνου και μνήμης για διαφορετικές εργασίες. Αργότερα σημειώθηκε ότι οι βασικές έννοιες των αναδρομικών συναρτήσεων και η θέση του Church είναι μάλλον υποθετικές.
Διατριβή Μ
Είναι σημαντικό να γίνει διάκριση μεταξύ της διατριβής του Turing και του ισχυρισμού ότι οτιδήποτε μπορεί να υπολογιστεί από μια υπολογιστική συσκευή μπορεί να υπολογιστεί από τη μηχανή της. Η δεύτερη επιλογή έχει τον δικό της ορισμό. Ο Γκάντι ονομάζει τη δεύτερη πρόταση «Θεσις Μ». Έχει ως εξής: «Ό,τι μπορεί να υπολογιστεί από μια συσκευή μπορεί να υπολογιστεί από μια μηχανή Turing». Με τη στενή έννοια της διατριβής, είναι μια εμπειρική πρόταση της οποίας η αξία αλήθειας είναι άγνωστη. Η διατριβή του Τούρινγκ και η «Θεσις Μ» μερικές φορές συγχέονται. Η δεύτερη εκδοχή είναι γενικά εσφαλμένη. Έχουν περιγραφεί διάφορες μηχανές υπό όρους που μπορούν να υπολογίσουν συναρτήσεις που δεν μπορούν να υπολογιστούν από τον Turing. Είναι σημαντικό να σημειωθεί ότι η πρώτη διατριβή δεν συνεπάγεται τη δεύτερη, αλλά συνάδει με την αναλήθεια της.
Αντίστροφη επίπτωση της διατριβής
Στη θεωρία υπολογισιμότητας, η διατριβή του Church χρησιμοποιείται ως περιγραφή της έννοιας της υπολογισιμότητας από μια κατηγορία γενικών αναδρομικών συναρτήσεων. Ο Αμερικανός Stephen Kleene έδωσε μια γενικότερη διατύπωση. Ονόμασε μερικώς αναδρομικές όλες τις μερικές συναρτήσεις υπολογίσιμες με αλγόριθμους.
Η αντίστροφη συνεπαγωγή αναφέρεται συνήθως ως αντίστροφη θέση της Εκκλησίας. Βρίσκεται στο γεγονός ότι κάθε αναδρομική συνάρτηση θετικών ακεραίων αξιολογείται αποτελεσματικά. Με στενή έννοια, μια διατριβή απλώς υποδηλώνει μια τέτοια πιθανότητα. Και με μια ευρύτερη έννοια, αφαιρείται από το ερώτημα εάν αυτή η υπό όρους μηχανή μπορεί να υπάρχει σε αυτήν.
Κβαντικοί υπολογιστές
Οι έννοιες των υπολογίσιμων συναρτήσεων και η διατριβή του Church έγιναν μια σημαντική ανακάλυψη για τα μαθηματικά, τη θεωρία μηχανών και πολλές άλλες επιστήμες. Όμως η τεχνολογία έχει αλλάξει πολύ και συνεχίζει να βελτιώνεται. Υποτίθεται ότι οι κβαντικοί υπολογιστές μπορούν να εκτελέσουν πολλές κοινές εργασίες με λιγότερο χρόνο από τους σύγχρονους. Όμως παραμένουν ερωτήματα, όπως το πρόβλημα της διακοπής. Ένας κβαντικός υπολογιστής δεν μπορεί να απαντήσει. Και, σύμφωνα με τη θέση Church-Turing, ούτε άλλη υπολογιστική συσκευή.
