MathJax

Σάββατο 29 Ιουλίου 2017

Ένα πρόγραμμα για τον τελεστή ελαχιστοποίησης

Μιλούσα προχθές για τη χρήση του τελεστή ελαχιστοποίησης (βήτα τάξης) ως τυπικού αντιπαραδείγματος για τη σφαλερή διαίσθηση οτι «άν ένα συναρτησιακό είναι μέγιστο, θά 'πρεπε νά 'ναι και ολικό». Στο μεταξύ έπεσα πάνω σε μιά ερώτηση στο στάκ εξτσέιντζ της πληροφορικής, σχετικά με την αποτελεσματικότητα του ενλόγω τελεστή (ή, για ν' ακριβολογούμε, μίας εκδοχής του: για κάθε κατηγόρημα στους φυσικούς παίρνουμε και έναν ανάλογο τελεστή ελαχιστοποίησης).

Η ερώτηση στο στάκ εξτσέιντζ τίθεται στα πλαίσια του κλασικού φορμαλισμού σχετικά με την αποτελεσματικότητα (τον πιάσαμε αυτόν τον φορμαλισμό και εδώ, όταν μιλούσαμε για έν' απ' τα πέιπερ του Μπέργκερ), οπου χρειάζεσαι μία αρίθμηση των ισόπεδων φυσικών που νά 'χει κάποιες συγκεκριμένες ιδιότητες, και λές έναν τελεστή απ' το \(\mathbb{N}\) στο \(\mathbb{N}\) αποτελεσματικό όταν συνοδεύεται απο μία αναδρομική συνάρτηση (εννοούμενη πάνω στους δείκτες της αρίθμησης), έτσι ωστε να καθιστά ένα συγκεκριμένο διάγραμμα (τελεστή, αναδρομικής συνάρτησης και αρίθμησης) μεταθετικό --για λεπτομέρειες, δές εδώ. Όλ' αυτά καλά και ζόρικα, αλλα κάπου εκεί έρχεται πάλι ο Μπάουερ και απαντά στην ερώτηση με το γνωστό του τρόπο: «η υπολογισιμότητα αφορά τον υπολογισμό· έ, γιατί δε χρησιμοποιείς υπολογιστή;».

Τετάρτη 26 Ιουλίου 2017

Ο τελεστής ελαχιστοποίησης δεύτερης τάξης είναι μέγιστος

Είναι κοινώς γνωστό στους κόλπους της ανώτερης υπολογισιμότητας, και συγκεκριμένα στη θεωρία πεδίων, οτι ο τελεστής ελαχιστοποίησης (δεύτερης τάξης), στα αγγλικά «minimization operator», είναι παράδειγμα συναρτησιακού που ενώ είναι μέγιστο δέν είναι ολικό, ωστόσο δύσκολα να βρεί κανείς απόδειξη γι' αυτό το πράγμα. Γιά να δούμε εδώ μια απόδειξη, που πατάει πάνω στα χνάρια του παραδείγματος 8.3.2 του [Stoltenberg-Hansen & al 1994].