Λογισμός Λάμδα

Στη Μαθηματική Λογική και στην Πληροφορική, λογισμός λάμδα ή λ-λογισμός ( λ-calculus), είναι ένα Τυπικό Σύστημα (formal system) σχεδιασμένο για την διερεύνηση ορισμών, εφαρμογών συναρτήσεων και αναδρομής συναρτήσεων.

Ετυμολογία[]

Η ονομασία "Λογισμός Λάμδα " σχετίζεται ετυμολογικά με το γράμμα "Λάμδα".

Εισαγωγή[]

Δημιουργήθηκε από τους Αλόνζο Τσερτς και Στέφεν Κλέινι τη δεκαετία 1930. Ο Τσερτς χρησιμοποίησε το λογισμό λάμδα για να δώσει αρνητική απάντηση στο Πρόβλημα Απόφασης (Entscheidungsproblem) του Hilbert. Ο λογισμός λάμδα μπορεί να χρησιμοποιηθεί για να ορίσει τι είναι μια υπολογίσιμη συνάρτηση.

Η ερώτηση αν δυο όροι του λογισμού λάμδα είναι ισοδύναμοι (Πρόβλημα Λέξης, word problem) δεν μπορεί να απαντηθεί με ένα γενικό αλγόριθμο. Αυτό ήταν το πρώτο πρόβλημα, πριν ακόμα το Πρόβλημα Τερματισμού (halting problem) για το οποίο μπορούσε να αποδειχθεί η μη αποφασιμότητα.

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

Τυπικός ορισμός[]

Ορισμός[]

Οι εκφράσεις (expressions) στο λογισμό λάμδα αποτελούνται από:

μεταβλητές v₁, v₂, . . . v_n

τα σύμβολα αφαίρεσης λ και .

παρενθέσεις ( )

Το σύνολο των εκφράσεων λάμδα, Λ, μπορεί να οριστεί αναδρομικά:

Αν x είναι μεταβλητή, τότε x $\in$ Λ
Αν x είναι μεταβλητή και M $\in$ Λ, τότε ( λ x . M ) $\in$ Λ
Αν M, N $\in$ Λ, τότε ( M N ) $\in$ Λ

Οι εκφράσεις που παράγονται από το 2 λέγονται αφαιρέσεις (abstractions) και από το 3 λέγονται εφαρμογές.

Συμβολισμός[]

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

Οι εξωτερικές παρενθέσεις παραλείπονται: M N αντί για (M N).

Οι εφαρμογές υποθέτουμε ότι συσχετίζονται προς τα αριστερά: M N P σημαίνει (M N) P.

Το σώμα μιας αφαίρεσης εκτείνεται όσο είναι δυνατόν προς τα δεξιά: λ x. M N σημαίνει (λ x.M N) και όχι (λ x. M) N

Σειρές από αφαιρέσεις συμπτύσσονται: λ x λ y λ z. N γράφεται συμπεπτυγμένα λ x y z . N

Ελεύθερες και δεσμευμένες μεταβλητές[]

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

Μεταβλητές που εμπίπτουν εντός της επίδρασης ενός τελεστή λ λέγονται δεσμευμένες. Όλες οι άλλες μεταβλητές λέγονται ελεύθερες.

Για παράδειγμα στην ακόλουθη έκφραση το y είναι δεσμευμένη μεταβλητή και το x είναι ελεύθερη:

λ y . xxy

Παρατηρήστε ότι κάθε μεταβλητή δεσμεύεται από το "πλησιέστερο" λάμδα. Στην ακόλουθη έκφραση η (μόνη) εμφάνιση του x δεσμεύεται από το δεύτερο λάμδα:

λ x . y (λ x . z x)

Το σύνολο των ελεύθερων μεταβλητών μιας έκφρασης λάμδα, M, συμβολίζεται με FV(M) και ορίζεται αναδρομικά ως:

FV( x ) = {x}, όπου x είναι μεταβλητή
FV ( λ x . M ) = FV ( M ) - {x}
FV ( M N ) = FV ( M ) $\cup$ FV ( N )

Μια έκφραση που δεν περιέχει ελεύθερες μεταβλητές λέγεται κλειστή. Οι κλειστές εκφράσεις λάμδα λέγονται και combinators και αντιστοιχούν σε όρους στη Συνδυαστική Λογική.

Υποσημειώσεις[]

Εσωτερική Αρθρογραφία[]

Βιβλιογραφία[]

Ιστογραφία[]

Κίνδυνοι Χρήσης

Αν και θα βρείτε εξακριβωμένες πληροφορίες
σε αυτήν την εγκυκλοπαίδεια
ωστόσο, παρακαλούμε να λάβετε σοβαρά υπ' όψη ότι
η "Sciencepedia" δεν μπορεί να εγγυηθεί, από καμιά άποψη,
την εγκυρότητα των πληροφοριών που περιλαμβάνει.

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

Πρέπει να λάβετε υπ' όψη ότι
όλα τα άρθρα μπορεί να είναι ακριβή, γενικώς,
και για μακρά χρονική περίοδο,
αλλά να υποστούν κάποιο βανδαλισμό ή ακατάλληλη επεξεργασία,
ελάχιστο χρονικό διάστημα, πριν τα δείτε.

Επίσης,
Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)"
(όχι μόνον, της Sciencepedia
αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)),
αν και άκρως απαραίτητοι,
είναι αδύνατον να ελεγχθούν
(λόγω της ρευστής φύσης του Web),
και επομένως είναι ενδεχόμενο να οδηγήσουν
σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο.
Ο αναγνώστης πρέπει να είναι
εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

>>Διαμαρτυρία προς την wikia<<

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)