Ο τεράστιος ηλεκτρονικός υπολογιστής,μεγέθους ενός καθεδρικού ναού, περιείχε όλες τις πληροφορίες που υπήρχαν στην Γη,οι δε συνδυαστικές του δυνατότητες ήταν κυριολεκτικά απεριόριστες.Είχε παίξει (ακόμα και με τον εαυτό του) όλες τις δυνατές παρτίδες σκάκι, είχε διαβάσει όλα τα βιβλία, είχε φανταστεί ακόμα και αυτά που δεν είχαν γραφτεί ακόμα, είχε ονειρευτεί όλα τα όνειρα κι είχε ξαναζήσει όλες τις ζωές στα ανεξάντλητα κυκλώματα του. Τον είχαν κατασκευάσει και προγραμματίσει για να του υποβάλλουν την οριστική ερώτηση, και στο τέλος την υπέβαλλαν:
"Υπάρχει Θεός;"
"Τώρα ναι" απάντησε η μηχανή-και ανελήφθη εις τους ουρανούς.
Deus ex machina, Κάρλο Φραμπέτι
Σαν σήμερα στο μαθηματικό συμπάν, το 1912, γεννήθηκε ο μαθηματικός και πιονιέρος προγραμματιστής Άλαν Τουρινγκ.
O Άλλαν Τούρινγκ γεννήθηκε στην Αγγλία το 1912.Μαθητης
ιδιαίτερων ικανοτήτων,έδειξε από πολύ μικρή ηλικία μεγάλη κλίση στα μαθηματικά και στην
φυσική.Το 1931,μπήκε στο πανεπιστήμιο του Κέιμπριτζ, όπου ασχολήθηκε με την
δουλειά του Kurt Godel πάνω στο
πρόβλημα της εγγενούς μη πληρότητας κάθε
λογικού συστήματος. Τρία χρόνια πριν , είχε εκδώσει μια μελέτη σχετικά με την πιθανότητα
κατασκευής μηχανών που θα ήταν ικανές να υπολογίσουν διαφόρους αλγορίθμους,
όπως το άθροισμα, ο πολλαπλασιασμός
κ.λ.π.
Ωθούμενος από την δουλειά του Godel ,προχώρησε ακόμα παραπέρα την
ιδέα του και προσδιόρισε το 1937, τις αρχές μια "παγκόσμιας"
μηχανής,ικανής να προσομοιώσει και εκτελέσει κάθε αλγόριθμο. Της μηχανής
Τούρινγκ.Έτσι τέθηκε ένα από τα θεμέλια του θεωρητικού οικοδομήματος της
σύγχρονης πληροφορικής.Δυο χρόνια πριν από την επαναστατική του συνεισφορά, ο Τούρινγκ ήρθε σε επαφή με το έργο του μεγάλου Ούγγρου μαθηματικού John Von Newman ,που θεωρούνταν ο άλλος πατέρας
της πληροφορικής , του πρόσφερε μια θέση στο Πρίνστον, με πολύ καλή αμοιβή και
εξαιρετικό κύρος.Ωστόσο ο Τούρινγκ
προτίμησε την μποέμικη ατμόσφαιρα του Κέιμπριτζ και απέρριψε την
προσφορά. Το 1939 μπήκε στην βρετανική υπηρεσία κρυπτογραφικής ανάλυσης του Bletchley Park .Παρότι παρασημοφορήθηκε από την
τάξη της Βρετανικής αυτοκρατορίας για την συνεισφορά του την περίοδο του
πόλεμου, η ομοφυλοφιλία του είχε ως αποτέλεσμα την απόρριψη του από την
ακαδημαϊκή κοινότητα. Θύμα βαθιάς κατάθλιψης,ο Τούρινγκ αυτοκτόνησε στις 8
Ιουνίου του 1954, τρώγοντας ένα μήλο με κυανιούχο κάλιο. Κυκλοφορεί ευρέως, στο
διαδίκτυο ο αστικός μύθος ότι από το συμβάν προέκυψε το λογότυπο της Apple .
O Τούρινγκ,το 1950 σε ένα άρθρο του για την πιθανότητα ανάπτυξης τεχνητής νοημοσύνης είχε επινοήσει ένα τεστ που θα ελέγχει σε μια συζήτηση μέσω μηνυμάτων αν η επικοινωνία γίνεται με άνθρωπο ή υπολογιστή .
Στο άρθρο αυτό, με τίτλο " Υπολογιστικές μηχανές και νοημοσύνη" ο Τούρινγκ γράφει:
...πιθανόν δεν θα είχε καμία αντίρρηση να δεχτεί ως δοκιμασία το παιχνίδι της μίμησης .Το παιχνίδι αυτό,γνωστό ως η "προφορική εξέταση",χρησιμοποιείται συχνά για να ανακαλύψουμε αν ένα πρόσωπο έχει κατανοήσει πραγματικά κάτι ή αν απλώς το έχει αποστηθίσει.Ας ακούσουμε ένα απόσπασμα από μια τέτοια προφορική εξέταση.
ΑΝΑΚΡΙΤΉΣ: Στον πρώτο στίχο του σονέτου σας που λέει "θα σε παρομοιάσω με μια μέρα ανοιξιάτικη",δεν θα ταίριαζε το ίδιο καλά ίσως καλύτερα η φράση "με μια μέρα του Μαγιού";
ΜΑΡΤΥΡΑΣ:Δεν θα συμφωνούσε το μέτρο.
ΑΝΑΚΡΙΤΗΣ:Τι θα λέγατε για "μια μέρα χειμωνιάτικη";Αυτό θα συμφωνούσε με το μέτρο μια χαρά.
ΜΑΡΤΥΡΑΣ:Ναι,αλλά κάνεις δεν θα ήθελε να τον παρομοιάσουν με μια χειμωνιάτικη μέρα.
ΑΝΑΚΡΙΤΗΣ:Θα λέγατε ότι ο κύριος Pickwick σας θυμίζει Χριστούγεννα; (ήρωας του Καρόλου Ντίκενς)
ΜΑΡΤΥΡΆΣ: Κατά κάποιο τρόπο,ναι.
ΑΝΑΚΡΙΤΗΣ:Και όμως,τα Χριστούγεννα είναι μέρα χειμωνιάτικη και δεν νομίζω πως η παρομοίωση θα ενοχλούσε τον κύριο PIckWick.
ΜΑΡΤΥΡΑΣ:Μάλλον αστειεύεστε.Λέγοντας" μια μέρα χειμωνιάτικη" ,εννοούμε μια συνηθισμένη χειμωνιάτικη μέρα και όχι μια μέρα εξαιρετική, όπως τα Χριστούγεννα.
O Τούρινγκ,το 1950 σε ένα άρθρο του για την πιθανότητα ανάπτυξης τεχνητής νοημοσύνης είχε επινοήσει ένα τεστ που θα ελέγχει σε μια συζήτηση μέσω μηνυμάτων αν η επικοινωνία γίνεται με άνθρωπο ή υπολογιστή .
Στο άρθρο αυτό, με τίτλο " Υπολογιστικές μηχανές και νοημοσύνη" ο Τούρινγκ γράφει:
...πιθανόν δεν θα είχε καμία αντίρρηση να δεχτεί ως δοκιμασία το παιχνίδι της μίμησης .Το παιχνίδι αυτό,γνωστό ως η "προφορική εξέταση",χρησιμοποιείται συχνά για να ανακαλύψουμε αν ένα πρόσωπο έχει κατανοήσει πραγματικά κάτι ή αν απλώς το έχει αποστηθίσει.Ας ακούσουμε ένα απόσπασμα από μια τέτοια προφορική εξέταση.
ΑΝΑΚΡΙΤΉΣ: Στον πρώτο στίχο του σονέτου σας που λέει "θα σε παρομοιάσω με μια μέρα ανοιξιάτικη",δεν θα ταίριαζε το ίδιο καλά ίσως καλύτερα η φράση "με μια μέρα του Μαγιού";
ΜΑΡΤΥΡΑΣ:Δεν θα συμφωνούσε το μέτρο.
ΑΝΑΚΡΙΤΗΣ:Τι θα λέγατε για "μια μέρα χειμωνιάτικη";Αυτό θα συμφωνούσε με το μέτρο μια χαρά.
ΜΑΡΤΥΡΑΣ:Ναι,αλλά κάνεις δεν θα ήθελε να τον παρομοιάσουν με μια χειμωνιάτικη μέρα.
ΑΝΑΚΡΙΤΗΣ:Θα λέγατε ότι ο κύριος Pickwick σας θυμίζει Χριστούγεννα; (ήρωας του Καρόλου Ντίκενς)
ΜΑΡΤΥΡΆΣ: Κατά κάποιο τρόπο,ναι.
ΑΝΑΚΡΙΤΗΣ:Και όμως,τα Χριστούγεννα είναι μέρα χειμωνιάτικη και δεν νομίζω πως η παρομοίωση θα ενοχλούσε τον κύριο PIckWick.
ΜΑΡΤΥΡΑΣ:Μάλλον αστειεύεστε.Λέγοντας" μια μέρα χειμωνιάτικη" ,εννοούμε μια συνηθισμένη χειμωνιάτικη μέρα και όχι μια μέρα εξαιρετική, όπως τα Χριστούγεννα.
Το
καλοκαίρι, ένα πρόγραμμα υπολογιστή σχεδιασμένο από το μηχανικό λογισμικού
Βλαντιμίρ Βεσέλοφ κατάφερε να πείσει 10 από τους 30 κριτές που
"συζήτησαν" μαζί του ότι είναι ο Γιουτζίν Γκούστμαν, ένα αγόρι
13 χρονών απο την Ουκρανία,και να περάσει το
τεστ.
Μηχανη
Turing απο την Lego.
Ένα σχετικό βίντεο για την ζωη του
Μοναδική και ιδιαίτερη η περίπτωση Turing, οπότε θα τολμήσω με τη σειρά μου μια αναφορά στη μνήμη του με έναν μαθηματικό γρίφο που με απασχόλησε στο παρελθόν.
ΑπάντησηΔιαγραφήΈνας ψύλλος robot είναι προγραμματισμένος να κινείται στο επίπεδο Ζ^2 των ακεραίων. Δεν είναι γνωστό το πρόγραμμα κίνησης με το οποίο είναι εφοδιασμένος, ούτε από το ποιο σημείο του επιπέδου ξεκίνησε. Ο ψύλλος αυτός σας ενοχλεί και θέλετε να τον σκοτώσετε. Μπορείτε κάθε ακέραια χρονική στιγμή να χτυπάτε ένα ακέραιο σημείο του επιπέδου, με την ελπίδα ο ψύλλος να βρίσκεται τη στιγμή εκείνη εκεί, οπότε και θα τον σκοτώσετε. Δε βλέπετε όμως πού είναι κάθε στιγμή (παρά μόνο αφού τον σκοτώσετε). Υπάρχει μέθοδος χτυπημάτων που εξασφαλίζει την εξόντωση του ψύλλου αργά η γρήγορα; (τα χτυπήματα αρχίζουν από τη χρονική στιγμή 1)
Για όσους θέλουν να το προσπαθήσουν, συνιστώ να εξετάσουν αρχικά την απλούστερη περίπτωση στην οποία ο ψύλλος τη χρονική στιγμή 0 βρίσκεται στο σημείο (0,0) και κάθε στιγμή μετακινείται κατά σταθερό διάνυσμα (χ,ψ), όπου χ,ψ άγνωστοι ακέραιοι.
ΑπάντησηΔιαγραφήΜε την ίδια περίπου φιλοσοφία, ως προς τη λύση είναι και το κατωτέρω πρόβλημα:
ΑπάντησηΔιαγραφήΔεκαέξι σπηλιές βρίσκονται στη σειρά, η μία μετά την άλλη. Ο σερίφης Μεγαλοφρύδης γνωρίζει ότι ένας ληστής, ο Φευγάτος Τζο, κρύβεται σε μία από τις σπηλιές. Ο σερίφης γνωρίζει επίσης ότι οι φίλοι του Φευγάτου Τζο τον έχουν συμβουλέψει να μετακινείται κάθε νύχτα στη διπλανή σπηλιά, είτε δεξιά είτε αριστερά. Ο σερίφης και οι βοηθοί του μπορούν να ερευνήσουν μόνο μία σπηλιά κάθε μέρα. Αν αρχίσουν να ερευνούν τις σπηλιές την πρώτη Μαΐου, Θα συλλάβουν τον κακοποιό πριν το τέλος του Μαΐου;
Περιοδικό Quantum
Πρόκειται για εντελώς διαφορετικά προβλήματα με εντελώς διαφορετικές λύσεις, Κάρλο. Μια βασική διαφορά τους είναι ότι οι σπηλιές είναι πεπερασμένες, αλλά τα ακέραια σημεία του επιπέδου άπειρα. Επίσης το πρόβλημα του ψύλλου σχετίζεται, όπως προανέφερα, με τον Turing (και κάποιο σημαντικό εύρημα του), ενώ αυτό που αναφέρεις δεν έχει καμία σχέση.
ΔιαγραφήΘα μπορούσαμε ωστόσο να αξιοποιήσουμε το γεγονός ότι τα ακέραια σημεία του επιπέδου είναι μεν άπειρα, αλλά αριθμήσιμα..
ΑπάντησηΔιαγραφήΑνέβασες το επίπεδο κατακόρυφα,Θανάση .Το πρόβλημα προφανώς και δεν είναι στοιχειώδες,πέρυσι τον Αύγουστο το είχε πάρει το μάτι μου στο διαδίκτυο σε έναν εξαιρετικό ιστότοπο.Ας περιμένουμε να δούμε
ΔιαγραφήΑσφαλώς και δεν είναι στοιχειώδες το πρόβλημα ΘΑΝΑΣΗ, αλλά πώς θα μπορούσε να είναι τέτοιο ένα πρόβλημα που αναφέρεται στον Turing; Δεν είναι όμως και απροσπέλαστο νομίζω. Στον 'εξαιρετικό ιστότοπο' που λες, αν εννοούμε τον ίδιο, θα γίνει φυσικά η οφειλόμενη μνεία κάποια στιγμή.
ΔιαγραφήΈχεις δίκιο Θανάση. Συνδύασα τις σπηλιές με τα επίπεδα, γι' αυτό το ανέφερα.
ΑπάντησηΔιαγραφήΧθες αναρτήθηκε ένα πρόβλημα που έστειλα στον Κώστα. Θα ήθελα και τη δική σου άποψη.
Για την περίπτωση που ο ψύλλος τη στιγμή 0 βρίσκεται στο σημείο (0,0) και κάθε στιγμή μετατοπίζεται κατά σταθερό διάνυσμα δ=(χ,ψ), ας σκεφτούμε ότι το δ μπορεί να είναι οποιοδήποτε μέλος του συνόλου (καρτεσιανού γινόμενου) Ζ×Ζ. Το Ζ×Ζ όμως είναι ένα αριθμήσιμο απειροσύνολο, δηλαδή μπορούμε να βάλουμε τα μέλη του σε μια σειρά 1,2,3,... (ας θυμηθούμε π.χ. τον τρόπο αρίθμησης των ρητών). Έτσι μπορούμε να γράψουμε:
ΑπάντησηΔιαγραφήΖ×Ζ = {δ1,δ2,δ3,...}
και τα χτυπήματα μας μπορούν να γίνονται ως εξής:
Τη στιγμή t=1 χτυπάμε το σημείο 1*δ1
Τη στιγμή t=2 χτυπάμε το σημείο 2*δ2
............................
Τη στιγμή t=ν χτυπάμε το σημείο ν*δν
..........................
Έτσι, όποιο κι αν είναι το διάνυσμα μετατόπισης του ψύλλου, κάποια στιγμή είναι βέβαιο ότι θα τον πετύχουμε.
Τι γίνεται όμως όταν το διάνυσμα μετατόπισης του ψύλλου δεν είναι απαραίτητα σταθερό, ενώ δεν ξέρουμε ούτε από ποιο σημείο ξεκινάει ο ψύλλος τη στιγμή 0;
Μια και χαράξαμε λοιπόν μια βασική γραμμή σκέψης, ας την τραβήξουμε λιγάκι πιο μακριά να δούμε μέχρι πού μπορεί να μας πάει:
ΑπάντησηΔιαγραφήΞέρουμε ότι ο ψύλλος είναι εφοδιασμένος με ένα πρόγραμμα που για κάθε χρονική στιγμή t (= 1, 2, 3,...) υπολογίζει τις συντεταγμένες ενός ακέραιου σημείου Π(t) = [χ(t),ψ(t)] και στέλνει το ψύλλο την κάθε στιγμή στο αντίστοιχο σημείο του επιπέδου.
Το σύνολο Ω των προγραμμάτων (με ένα από τα οποία έχει εφοδιαστεί ο ψύλλος) είναι άπειρο, ΑΛΛΑ κάθε πρόγραμμα δεν είναι τίποτε άλλο από μια ακολουθία πεπερασμένου πλήθους συμβόλων. Μπορούμε λοιπόν να πούμε ότι και το σύνολο Ω είναι αριθμήσιμο, αφού μπορούμε με κάποιον τρόπο να γράψουμε ένα-ένα όλα τα πιθανά προγράμματα με μια σειρά (π.χ. κατά αύξον πλήθος συμβόλων, αλφαβητικά κ.ο.κ) δηλαδή τελικά να γράψουμε:
Ω= {Π1(t), Π2(t), Π3(t), ...}
και τα χτυπήματά μας πλέον να γίνουν ως εξής:
Τη στιγμή t=1 χτυπάμε το σημείο Π1(1)
Τη στιγμή t=2 χτυπάμε το σημείο Π2(2)
............................
Τη στιγμή t=ν χτυπάμε το σημείο Πν(ν)
..........................
Μπορούμε λοιπόν κι εδώ να πούμε ότι, όποιο κι αν είναι το πρόγραμμα με το οποίο είναι εφοδιασμένος ο ψύλλος, κάποια στιγμή είναι βέβαιο ότι θα τον πετύχουμε ???
Εδώ είναι που έρχεται ο Turing και μάς προσγειώνει στη μίζερη πραγματικότητα...
Ο Τουριγκ θα έλεγε ότι δεν υπάρχει γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου δηλαδή ότι δεν μπορούμε να ξέρουμε αν ένα πρόγραμμα θα τελειώσει κάποτε, καλή ώρα τα Π1, Π2, Π3, ..
ΔιαγραφήΑκριβώς ΘΑΝΑΣΗ! Για να είναι αποτελεσματική η μέθοδος χτυπημάτων που αναφέραμε πιο πάνω, θα ήταν απαραίτητος ένας αλγόριθμος που να μας απαντάει αν ο εκάστοτε συνδυασμός προγράμματος Π – εισόδου t τερματίζει ή όχι, έτσι ώστε να εξαιρέσουμε από την αρίθμησή μας τα προγράμματα που δεν τερματίζουν. Αλλά, όπως ακριβώς το είπες, ο Turing έδειξε ότι το πρόβλημα του τερματισμού (the halting problem) δεν είναι αποφασίσιμο, κοντολογίς τέτοιος αλγόριθμος δεν υπάρχει.
ΑπάντησηΔιαγραφήΤο όμορφο (νομίζω) αυτό πρόβλημα δημοσιεύτηκε πριν από ένα χρόνο περίπου στον εξαιρετικό ιστότοπο των καθηγητών Κολουντζάκη, Μήτση κ.ά. του Πανεπιστημίου Κρήτης. Για περισσότερα, δίνω και τον σχετικό σύνδεσμο:
https://kolount.wordpress.com/2017/08/28/μπορείτε-να-σκοτώσετε-τον-ψύλλο/#comments