Βικιπαίδεια

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

Περιήγηση ιστορικού διαδραστικά
← Προηγούμενη διαφοράΕπόμενη διαφορά →
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
ΟπτικήΚώδικας wiki
Χωρίς σύνοψη επεξεργασίας
Χωρίς σύνοψη επεξεργασίας
Γραμμή 36:
Η Αναδρομή θεωρία προέρχεται από τη δεκαετία του 1930, με το έργο του [[Kurt Gödel , Alonzo Church , Alan Turing , Stephen Kleene]] και [[Emil Post]].
 
Τα θεμελιώδη αποτελέσματα που αποκόμισαν οι ερευνητές εγκαθίδρυσαν την ανδιαρθρωτική[[αναδιαρθρωτική υπολογισιμότητα]] ως σωστή επισημοποίησης της άτυπης ιδέα του αποτελεσματικού υπολογισμού. Αυτά τα αποτελέσματα οδήγησαν τον [[Stephen Kleene]] (1952) για να πλάσει τα δύο ονόματα "Church's thesis" (Kleene 1952:300) και «Turing's Thesis» (Kleene 1952:376). Σήμερα αυτά συχνά θεωρούνται ως μια ενιαία υπόθεση η [[Church–Turing]] [[thesis]] η οποία ορίζει ότι κάθε λειτουργία που είναι υπολογίσιμη από τον αλγόριθμο είναι μια υπολογίσιμη συνάρτηση . Αν και αρχικά σκεπτικός, από το 1946 ο Gödel τάχθηκε υπέρ αυτής της διατριβής:
 
"Ο Tarski τόνισε στην ομιλία του (και νομίζω δικαίως) τη μεγάλη σημασία της έννοιας της γενικής αναδρομής (ή του υπολογιστικού περιβάλλοντος του Turing). Μου φαίνεται ότι η σημασία αυτή σε μεγάλο βαθμό οφείλεται στο γεγονός ότι με αυτήν την έννοια για πρώτη φορά κατόρθωσε κάποιος να δώσει μια απόλυτη έννοια σε μια ενδιαφέρουσα επιστημολογική αντίληψη, δηλαδή χωρίς να εξαρτάται από τον φορμαλισμό που επιλέγεται. (Gοdel 1946 στο Davis 1965:84).
Ανακτήθηκε από "https://el.wikipedia.org/wiki/Θεωρία_υπολογισιμότητας"