Θεωρία πεδίων

Η **θεωρία πεδίων** (αγγλ. **domain theory**) είναι κλάδος των μαθηματικών που μελετά είδη μερικά διατεταγμένων συνόλων (partially ordered sets ή posets), τα οποία ονομάζονται **πεδία** (**domains**). Για αυτό το λόγο η θεωρία πεδίων μπορεί να θεωρηθεί σαν κλάδος της θεωρίας διάταξης (order theory). Έχει σημαντικές εφαρμογές στη θεωρητική πληροφορική, όπου χρησιμοποιείται για τον ορισμό της δηλωτικής σημασιολογίας, ειδικά για τις συναρτησιακές γλώσσες προγραμματισμού. Η θεωρία πεδίων εκφράζει με τυπικό τρόπο τις ιδέες της προσέγγισης (approximation) και της σύγκλισης (convergence) με γενικό τρόπο και έχει στενή σχέση με την τοπολογία. Στην επιστήμη υπολογιστών χρησιμοποιούνται εναλλακτικά οι μετρικοί χώροι.

## Εισαγωγή

Το βασικό κίνητρο για τη μελέτη των πεδίων, που άρχισε στα τέλη της δεκαετίας του 1960 από τον Dana Scott, ήταν η αναζήτηση δηλωτικής σημασιολογίας για το λ-λογισμό. Σε αυτό το τυπικό σύστημα, οι "συναρτήσεις" ("functions") ορίζονται από συγκεκριμένους όρους της γλώσσας. Μπορεί κανείς να μεταβεί από απλές συναρτήσεις σε συναρτήσεις που δέχονται σαν ορίσματα άλλες συναρτήσεις, με πλήρως συντακτικό τρόπο. Κάνοντας χρήση μόνο των συντακτικών μετασχηματισμών που παρέχονται, μπορεί κανείς να φτάσει στους λεγόμενους συνδυαστές σταθερού σημείου (fixed point combinators), με γνωστότερο παράδειγμα το συνδυαστή-Υ (Y combinator) - οι συνδυαστές αυτοί έχουν εξ ορισμού την ιδιότητα *f*(**Y**(*f*)) = **Y**(*f*) για κάθε συνάρτηση *f*.

Για τον τυπικό ορισμό δηλωτικής σημασιολογίας, πρέπει πρώτα να κατασκευαστεί ένα *μοντέλο* του λ-λογισμού, στο οποίο μια πλήρης (total) συνάρτηση αντιστοιχίζεται σε κάθε λ-όρο. Ένα τέτοιο μοντέλο θα τυποποιούσε τη σχέση μεταξύ του λ-λογισμού σαν πλήρως συντακτικού συστήματος, και του λ-λογισμού σαν σύστημα σημειογραφίας για το χειρισμό μαθηματικών συναρτήσεων. Δυστυχώς, τέτοιο μοντέλο δε μπορεί να υπάρξει, γιατί αν υπήρχε θα έπρεπε να περιέχει μια πλήρη συνάρτηση που να αντιστοιχεί στο συνδυαστή **Y**, δηλαδή μια συνάρτηση που να υπολογίζει το σταθερό σημείο (fixed point) οποιασδήποτε συνάρτησης *f*.  Για την περίπτωση του **Y** δε μπορεί να υπάρξει τέτοια συνάρτηση γιατί κάποιες συναρτήσεις (όπως η συνάρτηση *επόμενο*, αγγλ. *successor function*) δεν έχουν σταθερό σημείο. Στην καλύτερη περίπτωση, η συνάρτηση που θα αντιστοιχούσε στον **Y** θα έπρεπε να είναι μερική συνάρτηση (partial function), δηλαδή να μην ορίζεται για κάποιες τιμές της εισόδου.

Ο Scott απέφυγε αυτή τη δυσκολία τυποποιώντας μια έννοια "μερικής" ("partial") ή "ημιτελούς" ("incomplete") πληροφορίας για την αναπαράσταση υπολογισμών που ακόμα δεν έχουν επιστρέψει αποτέλεσμα. Αυτό μοντελοποιήθηκε θεωρώντας για κάθε πεδίο υπολογισμών (όπως οι φυσικοί αριθμοί), ένα επιπλέον στοιχείο που αναπαριστά τη *μη ορισμένη* (*undefined*) έξοδο, δηλ. το "αποτέλεσμα" ενός υπολογισμού που ποτέ δεν τερματίζει. Επιπλέον, το πεδίο των υπολογισμων εφοδιάζεται με μια *σχέση διάταξης* (*ordering relation*), στην οποία το "μη ορισμένο αποτέλεσμα" είναι το ελάχιστο στοιχείο (least element).

Το βασικό βήμα για την εύρεση ενός μοντέλου για το λ-λογισμό είναι να εξετάζονται μόνο οι συναρτήσεις (στο μερικά διατεταγμένο σύνολο) που εγγυημένα έχουν ελάχιστα σταθερά σημεία. Το σύνολο αυτών των συναρτήσεων, μαζί με την κατάλληλη διάταξη, είναι το "πεδίο" κατά τη θεωρία. Ο περιορισμός όμως σε ένα υποσύνολο από όλες τις διαθέσιμες συναρτήσεις έχει άλλο ένα θετικό αποτέλεσμα: μπορούν να υπάρξουν πεδία που περιέχουν τον ίδιο το χώρο συναρτήσεών τους (function space), δηλαδή με συναρτήσεις που να μπορούν να εφαρμοστούν στον εαυτό τους.

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

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

## Οδηγός για τους τυπικούς ορισμούς

Σε αυτήν την ενότητα εισάγονται οι βασικές έννοιες και ορισμοί της θεωρίας πεδίων. Η θεώρηση των πεδίων σαν *διατάξεων πληροφορίας* (*information orderings*) είναι η βάση στην οποία στηρίζεται η μαθηματική τυποποίηση που ακολουθεί. Οι ακριβείς τυπικοί ορισμοί βρίσκονται στα άρθρα για κάθε έννοια. Το λεξιλόγιο θεωρίας διάταξης (order theory glossary) περιέχει μια λίστα από γενικούς ορισμούς της διάταξης, που περιλαμβάνουν έννοιες της θεωρίας πεδίων.

Ακολουθούν οι βασικότερες έννοιες της θεωρίας πεδίων.

### Κατευθυνόμενα σύνολα σαν συγκλίνουσες προδιαγραφές

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

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

Όπως και στην περίπτωση των ακολουθιών, ενδιαφερόμαστε για το *όριο* (*limit*) ενός κατευθυνόμενου συνόλου. Σύμφωνα με όσα έχουν ήδη αναφερθεί, αυτό θα ήταν κάποιο στοιχείο που να αποτελεί τη γενικότερη πληροφορία που επεκτείνει την πληροφορία όλων των στοιχείων του κατευθυνόμενου συνόλου, δηλαδή το μοναδικό στοιχείο που περιέχει *ακριβώς* την πληροφορία που υπήρχε στο κατευθυνόμενο σύνολο και τίποτα άλλο. Στον τυπικό ορισμό της θεωρίας διάταξης, αυτό είναι απλά το *ελάχιστο άνω όριο* (**least upper bound**) του κατευθυνόμενου συνόλου. Όπως και στην περίπτωση των ορίων ακολουθιών, δεν είναι πάντα σίγουρο ότι υπάρχει ελάχιστο άνω φράγμα σε κάποιο κατευθυνόμενο σύνολο.

Συνήθως ενδιαφερόμαστε ιδιαίτερα για τα πεδία υπολογισμών στα όποια όλες οι συνεπείς προδιαγραφές *συγκλίνουν*, δηλ. για διατάξεις όπου όλα τα κατευθυνόμενα σύνολα έχουν ένα ελάχιστο άνω όριο. Η ιδιότητα αυτή ορίζει την κλάση των **κατευθυνόμενων πλήρων μερικών διατάξεων** (**directed complete partial orders** ή **dcpo**). Πράγματι, συχνά η θεωρία πεδίων εξετάζει διατάξεις που να είναι τουλάχιστον κατευθυνόμενες και πλήρεις.

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

### Υπολογισμοί και πεδία

Με τους παραπάνω βασικούς τυπικούς ορισμούς διαθέσιμους, οι υπολογισμοί πρέπει να είναι συναρτήσεις, που παίρνουν είσοδο από κάποιο πεδίο υπολογισμών και επιστρέφουν έξοδο στο ίδιο ή σε άλλο πεδίο. Η έξοδος μιας συνάρτησης θα πρέπει να περιέχει περισσότερη πληροφορία όσο αυξάνεται η πληροφορία της εισόδου, δηλαδή η συνάρτηση πρέπει να είναι **[[Μονοτονία συνάρτησης|μονότονη]]**.

Στην περίπτωση των **πλήρων μερικών διατάξεων**, είναι επιθυμητή η συμβατότητα των υπολογισμών με την κατασκευή των ορίων στο κατευθυνόμενο σύνολο. Τυπικά αυτό σημαίνει ότι, για κάποια συνάρτηση *f*, η απεικόνιση *f*(*D*) ενός κατευθυνόμενου συνόλου *D* (δηλαδή το σύνολο από απεικονίσεις κάθε στοιχείου του *D*) είναι κατευθυνόμενο σύνολο και έχει σαν ελάχιστο άνω όριο την απεικόνιση του ελάχιστου άνω ορίου του *D*. Η *f* τότε *διατηρεί τα κατευθυνόμενα μέγιστα* (*preserves directed suprema*). Επίσης, θεωρώντας κατευθυνόμενα σύνολα από δύο στοιχεία, μια τέτοια συνάρτηση πρέπει να είναι μονότονη. Από τις ιδιότητες αυτές προκύπτει η έννοιας μια συνάρτησης **συνεχούς κατά Scott** (**Scott-continuous**), που συχνά αποκαλείται και απλά *συνεχής συνάρτηση*.

### Προσέγγιση και πεπερασμένα σύνολα

Η θεωρία πεδίων είναι μια πλήρως *ποιοτική* προσέγγιση όσον αφορά τη μοντελοποίηση της δομής καταστάσεων πληροφορίας. Κάτι μπορεί να θεωρηθεί ότι έχει περισσότερη πληροφορία, χωρίς να ορίζεται πόση είναι η διαφορά σε σχέση με πριν. Υπάρχουν όμως περιπτώσεις που πρέπει να χειριστούμε στοιχεία που είναι κατά μια έννοια απλούστερα (ή λιγότερο πλήρη) από μια δεδομένη κατάσταση πληροφορίας. Για παράδειγμα, στη φυσική διάταξη των υποσυνόλων που περιέχονται σε άλλα, σε κάποιο δυναμοσύνολο (powerset), κάθε άπειρο στοιχείο (δηλ. σύνολο) παρέχει περισσότερη "πληροφορία" σε σχέση με οποιοδήποτε από τα *πεπερασμένα* υποσύνολά του.

Αν πρέπει να μοντελοποιηθεί μια τέτοια σχέση, πρέπει πρώτα να εξεταστεί η αυστηρή διάταξη *n* ∈ **N** *f* *n*(0).

## Γενικεύσεις
* Συνθετική θεωρία πεδίων (Synthetic domain theory)
* Τοπολογική θεωρία πεδίων (Topological domain theory)
* Ένα διάστημα συνέχειας (continuity space) είναι μια γενίκευση των μετρικών διαστημάτων και των μερικά διατεταγμένων συνόλων, και μπορεί να χρησιμοποιηθεί για να ενοποιήσει τις βασικές έννοιες των μετρικών χώρων και των πεδίων.

## Δείτε επίσης
* Πεδίο Scott
* Θεωρία τύπων
* Θεωρία κατηγοριών

## Βιβλιογραφία
*
*
*
*
*
*
*

Κατηγορία:Θεωρητική πληροφορική
Κατηγορία:Τυπική σημασιολογία