75 Xρόνια Eπιστήμης Yπολογιστών

[pgrontas]

Στις 28/05/1936 o Alan Turing έστειλε προς δημοσίευση την εργασία του "On Computable Numbers, With an Application to The Entscheidungsproblem", το οποίο θεωρείται από πολλούς το επίσημο σημείο εκκίνησης της επιστήμης της πληροφορικής.
Για όποιον ενδιαφέρεται το paper υπάρχει σε αρχείο pdf εδώ
Ένα πολύ ενδιαφέρον σχετικό βιβλίο είναι το The Annotated Turing του Charles Petzold, το οποίο περιέχει όλο το paper με λεπτομερή επεξήγηση σχεδόν για κάθε γραμμή του.

[Λάμπρος Μπουκουβάλας]

ενδιαφέρον Παναγιώτη.
το αναδημοσιεύω στο κεπληνέτ φωκίδας και στην ιστοσελίδα μου.

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

[Νίκος Αδαμόπουλος]

Στη δημοσίευση αυτή είχα αναφερθεί κι εγώ στο: https://alkisg.mysch.gr/steki/index.php?topic=3323.0 Στο post εκείνο αναφέρω το 1937 γιατί: "Turing's paper submitted 28 May 1936, published January 1937" ( http://en.wikipedia.org/wiki/Turing_machine )

Πέρα από το ότι η συγκεκριμένη εργασία "θεωρείται από πολλούς το επίσημο σημείο εκκίνησης της επιστήμης της πληροφορικής" και περιέγραψε την αποκαλούμενη πλέον Turing Machine, αποτελεί σημαντικό στοιχείο στην εξέλιξη των μαθηματικών αφού απαντάει στο πρόβλημα της αποφασισιμότητας του Χίλμπερτ, το Entscheidungsproblem στα γερμανικά.

Πιο συγκεκριμένα, στις αρχές του προηγούμενου αιώνα υπήρχε μια τάση στη σχετική έρευνα για την τακτοποίηση των θεμελίων των μαθηματικών. Στην προσπάθεια αυτή να οικοδομηθεί εκ νέου η μαθηματική γνώση, πρωτοστατούσε η πλέον εξέχουσα προσωπικότητα της εποχής εκείνης, ο Χίλμπερτ. Το 1900, σε μια ιστορική διάλεξη στη Διεθνή Συνδιάσκεψη των Μαθηματικών στο Παρίσι, ο Χίλμπερτ πρότεινε ένα πρόγραμμα έρευνας που συμπεριλάμβανε 10 άλυτα μέχρι τότε προβλήματα των μαθηματικών (αργότερα τα έκανε 23) που θεωρούσε άμεσης προτεραιότητας, τα περισσότερα από τα οποία επικεντρώνονταν στα λογικά θεμέλια της επιστήμης. Βλ. σχετικά στο: http://en.wikipedia.org/wiki/Hilbert's_problems

Ο Χίλμπερτ γενικά ήταν πολύ αισιόδοξος αφού εκείνη την εποχή είχε δηλώσει ότι "κάθε συγκεκριμένο μαθηματικό πρόβλημα θα πρέπει αναγκαστικά να επιδέχεται μια ακριβή λύση". Tο 1928 σε ένα συνέδριο διατύπωσε τα εξής ερωτήματα: 1) Είναι τα μαθηματικά πλήρη, με την έννοια του ότι κάθε πρόταση μπορεί να αποδειχθεί ορθή ή εσφαλμένη; 2) Είναι τα μαθηματικά συνεπή, με την έννοια ότι δεν μπορούμε ποτέ να καταλήξουμε σε αντιφάσεις ακολουθώντας μια σειρά έγκυρων αποδεικτικών βημάτων; 3) Είναι τα μαθηματικά αποφασίσιμα, δηλαδή υπάρχει συγκεκριμένη μέθοδος που θα μπορούσε να οδηγεί εγγυημένα σε μια ορθή απόφαση ως προς το αληθές μιας πρότασης;

Μέχρι τότε κανένα από αυτά τα ερωτήματα δεν είχε απαντηθεί, αν και ο Χίλμπερτ πίστευε ότι η απάντηση και στα τρία πρέπει να είναι "ναι".

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

Βλ. σχετικά παλιότερο post μου: https://alkisg.mysch.gr/steki/index.php?topic=2803.msg36863#msg36863

Ο Turing με τη συγκεκριμένη δημοσίευση το πήγε ακόμα παραπέρα. Ουσιαστικά απέδειξε την αδυναμία αποδείξεως του ότι μια συγκεκριμένη πρόταση είναι μη αποδείξιμη!

Συγκεκριμένα,  στο τέλος της προτελευταίας παραγράφου της σελίδας 262 του pdf, που αναφέρει ο Παναγιώτης, καταλήγει: "Hence the Entscheidungs-problem cannot be solved".

[Λάμπρος Μπουκουβάλας]

Νίκο, το έχεις το κιλό... 

[pgrontas]

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

Επίσης κάτι πολύ ενδιαφέρον είναι ότι στην εργασία αυτή μία 'καλή' μηχανή Turing δεν σταματά ποτέ την λειτουργία της. Όταν έχει ολοκληρωθεί ο υπολογισμός του αριθμού τυπώνει συνέχεια 0 για παράδειγμα ή  μια συγκεκριμένη ακολουθία από 0 και 1. Αυτό έρχεται σε αντίθεση με το Halting Problem που ξέρουμε σήμερα, το οποίο ναι μεν το συνέλαβε ο Turing αλλά το έφερε στην σημερινή του μορφή αργότερα ο Martin Davis. O Turing θεωρούσε ότι μία μηχανή 'σταματά' τον υπολογισμό όταν μπαίνει σε ένα απειρο loop που τυπώνει πάντα την ίδια ακολουθία.