CAPTCHA και οι αρχές της Πληροφορικής (ΜΕΡΟΣ 1)

Πρώτα απ' όλα: CAPTCHA = Completely Aytomated Public Turing test to tell Computers and Humans Apart = Πλήρως αυτοματοποιημένος έλεγχος Turing για τον διαχωρισμό Ανθρώπων και Υπολογιστών.

Ένα παράδειγμα CAPTCHA:

θυμίζουν τις εικόνες με τους χαρακτήρες που πρέπει να συμπληρώσουμε, όταν θέλουμε π.χ. να φτιάξουμε έναν λογαριασμό e-mail.

Οι κλασσικές αυτές εικόνες στις οποίες ένας άνθρωπος πρέπει να διαβάσει και να γράψει τα γράμματα αυτά, προκειμένου να μπορέσει να χρησιμοποιήσει κάποια διαδικτυακή υπηρεσία, ενώ παράλληλα να αποκλειστούν από αυτήν κακόβουλα προγράμματα (bots), τα οποία έχουν σαν στόχο την κακή χρήση (abuse) της υπηρεσίας αυτής, για την εκπλήρωση κάποιας σκοπιμότητας του δημιουργού τους. Τα CAPTCHA είναι διαμορφωμένα κατάλληλα, ώστε ένας άνθρωπος να μπορέσει να τα αποκωδικοποιήσει (όλοι διαβάζουμε τις λέξεις fellowing και finding στην εικόνα), ενώ παράλληλα να μην μπορούν να αναγνωριστούν (εύκολα και σε μικρό χρόνο) από οποιοδήποτε λογισμικό Η/Υ.

Για να μάθουμε τη λογική των CAPTCHA, και γενικότερα του Turing test, θα πρέπει να ξέρουμε το τι ακριβώς μπορεί να κάνει ένας υπολογιστής.

Το 1936 (κάπου), θεμελιώθηκε το δόγμα των Alan Turing και Alonzo Church (γνωστό σαν θέση των Church-Turing). Σε αυτό οριζόταν το ότι μια νοητή υπολογιστική μηχανή (μηχανή Turing) μπορεί να προσομοιώσει έναν προγραμματιστικό αλγόριθμο και το ακριβώς ανάποδό του, δηλαδή το ότι ένας αλγόριθμος μπορεί να εξομοιώσει τη λειτουργία μιας μηχανής Turing. Συνοπτικά, ότι δηλαδή η μηχανή Turing (ο υπολογιστής) είναι ΑΠΟΛΥΤΑ ισοδύναμος με το πρόγραμμα που εκτελεί (τον αλγόριθμο).

Ότι μπορεί να κάνει ένα κομμάτι του Η/Υ, μπορεί να το κάνει και ένα λογισμικό που συμπεριφέρεται όπως αυτό το κομμάτι του Η/Υ, και αντιστρόφως.

Επεξήγηση μερικων εννοιών:
Μια μηχανή Turing είναι το θεωρητικό μοντέλο ενός υπολογιστή. Οι δυνατότητές της είναι όσες μπορεί να έχει ένας υπολογιστής, όσο κι αν εξελιχθεί η τεχνολογία. Εχει μια άπειρης χωρητικότητας ταινία σαν μνήμη (δηλαδή μια άπεριόριστα μεγάλη μνήμη), μια κεφαλή που μπορούσε να εκτελέσει πράξεις εγγραφής και ανάγνωσης από/προς την ταινίας (προσομοιώνει την οποιαδήποτε συσκευή εισόδου εξόδου έχει ένας Η/Υ στην ουσία) και μια μονάδα ελέγχου, η οποία έχει ένα πεπερασμένο σύνολο καταστάσεων (δηλαδή ένα πλήθος καταστάσεων που το πλήθος τους μπορεί να μετρηθεί - δεν είναι άπειρα μεγάλο) μαζί με μια συνάρτηση (μαθηματική) που καθορίζει το πως ενώ η μηχανή βρίσκεται σε μια κατάσταση και έχει διαβάσει κάποιο δεδομένο από την ταινία, θα πρέπει να προχωρήσει στην επόμενη κίνηση.
Ένας αλγόριθμος είναι ένα σύνολο εντολών, που:
είναι αυστηρά καθορισμένες, δηλαδή είναι πράγματα που μπορούν να πραγματοποιηθούν. (π.χ. μια άκυρη εντολή για αλγόριθμο είναι η διαίρεση με το 0, που ως γνωστόν δεν ορίζεται).
μπορούν να πραγματοποιηθούν σε πεπερασμένο χρόνο, δηλαδή μπορεί να τελειώσουν σε 1 ώρα, 1 μέρα, 1 μήνα, 1 χρόνο, αλλά κάποια στιγμή θα τελειώσουν και θα δώσουν ένα αποτέλεσμα. Εντολές που εκτελούνται επ' άπειρο ΔΕΝ ΠΡΕΠΕΙ ΝΑ ΥΠΑΡΧΟΥΝ.
Η επιτυχής διεκπεραίωση του αλγόριθμου θα δώσει τη λύση ενός προβλήματος.

Ας δούμε έναν αλγόριθμο που χρησιμοποιούμε συνεχώς στην καθημερινή μας ζωή:

ΦΤΙΑΞΙΜΟ ΦΡΑΠΕ:

ΔΕΔΟΜΕΝΟ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ: ΤΟ ΠΩΣ ΠΡΟΤΙΜΑ ΤΟΝ ΚΑΦΕ ΤΟΥ Ο ΧΡΗΣΤΗΣ.
Π.Χ. "ΦΡΑΠΕ ΓΛΥΚΟ ΧΩΡΙΣ ΓΑΛΑ"
ΕΠΙΣΗΣ, ΤΟ ΟΤΙ ΑΥΤΟΣ ΠΟΥ ΘΑ ΦΤΙΑΞΕΙ ΚΑΦΕ, ΕΙΝΑΙ ΓΡΗΓΟΡΟΣ.

1) ΠΑΡΕ ΤΟ ΠΟΤΗΡΙ.

2)ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΦΡΑΠΕ ΓΛΥΚΟ, ΤΟΤΕ ΒΑΛΕ 3 ΚΟΥΤΑΛΙΕΣ ΖΑΧΑΡΗ.
3)ΑΛΛΙΩΣ, ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΦΡΑΠΕ ΜΕΤΡΙΟ, ΒΑΛΕ 1 Ή 2 ΚΟΥΤΑΛΙΕΣ.
4)ΑΛΛΙΩΣ, ΜΗΝ ΒΑΛΕΙΣ ΖΑΧΑΡΗ/

5)ΑΝ ΠΡΟΤΙΜΑΣ ΤΟΝ ΚΑΦΕ ΕΛΑΦΡΥ, ΒΑΛΕ 1 ΚΟΥΤΑΛΙΑ ΚΑΦΕ.
6)ΑΛΛΙΩΣ, ΒΑΛΕ ΟΣΕΣ ΝΟΜΙΖΕΙΣ.

7)ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΚΑΦΕ ΜΕ ΓΑΛΑ, ΒΑΛΕ 1 ΣΥΣΚΕΥΑΣΙΑ ΑΠΟ ΤΙΣ ΜΙΚΡΕΣ ΑΤΟΜΙΚΕΣ.
8)ΑΛΛΙΩΣ ΜΗ ΒΑΖΕΙΣ ΓΑΛΑ.

9)ΠΑΡΕ ΤΟ ΧΤΥΠΗΤΗΡΙ ΚΑΙ ΑΝΑΚΑΤΕΨΕ ΜΕ ΑΥΤΟ ΤΟ ΜΕΙΓΜΑ.
10)ΠΡΟΣΘΕΣΕ ΝΕΡΟ.
11)ΒΑΛΕ ΚΑΛΑΜΑΚΙ ΣΤΟ ΠΟΤΗΡΙ

12)ΤΕΛΟΣ, Ο ΚΑΦΕΣ ΕΧΕΙ ΓΙΝΕΙ.

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

Ας δούμε έναν ακόμα αλγόριθμο, για να καταλάβουμε το ΒΑΣΙΚΟ σημέιο της ΤΑΧΥΤΗΤΑΣ ΕΚΤΕΛΕΣΗΣ.

ΦΤΙΑΞΙΜΟ ΦΡΑΠΕ ΜΕ ΠΟΛΥ ΠΟΛΥ ΣΠΑΡΙΛΑ:

ΔΕΔΟΜΕΝΟ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ: ΤΟ ΠΩΣ ΠΡΟΤΙΜΑ ΤΟΝ ΚΑΦΕ ΤΟΥ Ο ΧΡΗΣΤΗΣ.
Π.Χ. "ΦΡΑΠΕ ΓΛΥΚΟ ΧΩΡΙΣ ΓΑΛΑ"
ΕΠΙΣΗΣ, ΤΟ ΟΤΙ ΑΥΤΟΣ ΠΟΥ ΘΑ ΦΤΙΑΞΕΙ ΚΑΦΕ, ΒΑΡΙΕΤΑΙ ΠΟΥ ΖΕΙ.

1) ΠΑΡΕ ΑΡΓΑ ΑΡΓΑ ΤΟ ΠΟΤΗΡΙ.

2)ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΦΡΑΠΕ ΓΛΥΚΟ, ΤΟΤΕ ΒΑΛΕ 3 ΚΟΥΤΑΛΙΕΣ ΖΑΧΑΡΗ, ΠΡΩΤΑ ΚΑΝΕ ΚΑΝΑ 5ΩΡΟ ΓΙΑ ΝΑ ΒΡΕΙΣ ΤΗ ΖΑΧΑΡΗ.
3)ΑΛΛΙΩΣ, ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΦΡΑΠΕ ΜΕΤΡΙΟ, ΒΑΛΕ 1 Ή 2 ΚΟΥΤΑΛΙΕΣ.
4)ΑΛΛΙΩΣ, ΜΗΝ ΒΑΛΕΙΣ ΖΑΧΑΡΗ/

5)ΑΝ ΠΡΟΤΙΜΑΣ ΤΟΝ ΚΑΦΕ ΕΛΑΦΡΥ, ΒΑΛΕ 1 ΚΟΥΤΑΛΙΑ ΚΑΦΕ. ΑΛΛΑ ΠΟΥ ΕΙΝΑΙ Ο ΚΑΦΕΣ (ΨΑΧΝΕΙ 1 ΩΡΑ) ΕΝΤΑΞΕΙ, ΤΟΝ ΒΡΗΚΑ!
6)ΑΛΛΙΩΣ, ΒΑΛΕ ΟΣΕΣ ΝΟΜΙΖΕΙΣ.

7)ΑΝ ΠΙΝΕΙΣ ΤΟΝ ΚΑΦΕ ΜΕ ΓΑΛΑ, ΒΑΛΕ 1 ΣΥΣΚΕΥΑΣΙΑ ΑΠΟ ΤΙΣ ΜΙΚΡΕΣ ΑΤΟΜΙΚΕΣ, ΠΟΥ ΕΧΕΙΣ ΞΕΧΑΣΕΙ ΝΑ ΠΑΡΕΙΣ, ΟΠΟΤΕ ΞΟΔΕΨΕ 10 ΩΡΕΣ ΝΑ ΠΑΣ ΣΤΟ SUPER MARKET ΝΑ ΠΑΡΕΙΣ .
8)ΑΛΛΙΩΣ ΜΗ ΒΑΖΕΙΣ ΓΑΛΑ.

9)ΠΑΡΕ ΤΟ ΧΤΥΠΗΤΗΡΙ ΚΑΙ ΑΝΑΚΑΤΕΨΕ ΜΕ ΑΥΤΟ ΤΟ ΜΕΙΓΜΑ. ΑΡΓΑ.
10)ΠΡΟΣΘΕΣΕ ΝΕΡΟ.
11)ΒΑΛΕ ΚΑΛΑΜΑΚΙ ΣΤΟ ΠΟΤΗΡΙ, ΑΦΟΥ ΠΡΩΤΑ ΡΩΤΗΣΕΙΣ ΤΟΝ ΕΞΟΡΓΙΣΜΕΝΟ ΠΕΛΑΤΗ ΤΗ ΟΜΑΔΑ ΕΙΝΑΙ ΓΙΑ ΝΑ ΒΑΛΕΙΣ ΚΑΙ ΤΟ ΚΑΤΑΛΛΗΛΟ ΧΡΩΜΑ

12)ΤΕΛΟΣ, Ο ΚΑΦΕΣ ΕΧΕΙ ΓΙΝΕΙ.

Με τον πρώτο αλγόριθμο, φτιάχνουμε καφέ σε 5 λεπτά, με τον δεύτερο σε 1 μέρα. Και με τους 2, το αποτέλεσμα θα είναι ότι φτιάξαμε καφέ. Ο αλγόριθμος είναι ακριβώς ο ίδιος, με την τροποποίση του ΑΡΓΑ.

Το αργά αυτό, μπορεί να θεωρηθεί σαν μια ΣΤΑΘΕΡΗ (ίση με ένα σταθερό, δηλαδή απαράλαχτο κάτω από οποιεσδήποτε συνθήκες) παράμετρος, η οποία καθορίζει το ΠΟΣΟ ΠΙΟ ΑΡΓΟΣ είναι ο αλγόριθμος "ΦΤΙΑΞΙΜΟ ΦΡΑΠΕ ΜΕ ΠΟΛΥ ΠΟΛΥ ΣΠΑΡΙΛΑ" από τον αλγόριθμο "ΦΤΙΑΞΙΜΟ ΦΡΑΠΕ".

(Συνεχίζεται...)

εξαιρετικη παρουσιαση

Που να δεις και τη συνέχεια!

Πίτσα!

Α, ξέχασα.


Φανταστείτε τη μηχανή Turing κάπως έτσι:



(Οι λεπτομέρειες είναι πάρα πολλές, αλλά δεν ενδιαφέρουν για τη συνέχεια του θέματος.)

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

*υποθέτω ότι κι αυτά που αναφέρω είναι κάποιο είδος CAPTCHA..

Γιώργος Τ. έγραψε:Εμένα πάντα με εκνεύριζαν αυτά!!! Ειδικά κάποια που έπαιζαν με τα χρώματα και έπρεπε να δεις γράμματα και αριθμούς πίσω από διάφορα χρώματα... Έχω και δυσχρωματοψία και ήταν εφιαλτικό κάτι τέτοιο για μένα...

*υποθέτω ότι κι αυτά που αναφέρω είναι κάποιο είδος CAPTCHA..

Ναι, captcha είναι. Αλλά αν έχεις πρόβλημα με αυτά, μπορείς να στείλεις mail στον διαχειριστή της υπηρεσίας για παράκαμψη του captcha και (μετά από κάτι μέρες) να γραφτείς κατευθείαν.

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

Και συνεχίζουμε! (Ξέρω, σας σπάω τα @@ με τις πληροφορικές μ****ιες μου, υπομονή, θα βγω για καφέ σε 3 ώρες.)

Αφού ξεκινήσαμε από τη μέθοδο του CAPTCHA για να δούμε το πως μπορεί ο άνθρωπος να περιορίσει τις δυνατότητες του υπολογιστή και ασχοληθήκαμε συνοπτικά με την ισοδυναμία hardware/software, το πως ο υπολογιστής λύνει προβλήματα και κάναμε μια νύξη για την ταχύτητα επίλυσης, ας προχωρήσουμε λίγο πιο βαθιά στο θέμα ταχύτητα, και ύστερα στο άλλο μεγάλο θέμα, το "τι ΔΕ μπορεί να κάνει ο υπολογιστής".

Και τώρα θα μου πει κανείς "τι με νοιάζει εμένα τι δε μπορεί να κάνει ο υπολογιστής;". Ναι, αλλά τον χρησιμοποιείς όμως, είναι καλό να το ξέρεις κι αυτό...


Υπάρχουν λοιπόν πολλοί διαφορετικοί (δηλαδή τεχνικές λύσης) του ίδιου προβλήματος, και στην επιστήμη και στην τεχνολογία και στην καθημερινή ζωή.
Επειδή όμως, κάτι ήξερε αυτός που έλεγε "ο χρόνος είναι χρήμα", πολλές φορές προσπαθούμε να βρίσκουμε τις καλύτερες δυνατές τεχνικές λύσεων. Μπορούμε π.χ. το (a+b)^2 (είναι το (a+b) "στο τετράγωνο") να το υπολογίσουμε σαν:
(a+b)*(a+b)=a*a+a*b+b*a+b*b=(a^2)+2*a*b+(b^2) που θέλει 4 πολλαπλασιασμούς και 2 προσθέσεις
ή σαν:
(a+b)*(a+b)=r*r=s (όπου r=το αποτέλεσμα του a+b και s=το αποτέλεσμα του r*r), που θέλει 2 προσθέσεις και 1 πολλαπλασιασμό.
(Οι πράξεις γίνονται με το χέρι εδώ.)

Ποιός τρόπος απ' τους 2 συμφέρει;


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

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

(συνεχίζεται...)

Και η συνέχεια (για το τέλος του πρώτου μέρους)...

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

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

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


(Τέλος πρώτου μέρους.)