SW wykład 9 - Slajd17

<<powrót do strony wykładu

Dziedziny podstawowe Suma i produkt Suma spłaszczona i produkt spłaszczony Przestrzeń funkcji ciągłych Izomorfizm dziedzin Konstruowanie funkcji ciągłych Złożenie funkcji i indeksowanie Inne konstrukcje Operator punktu stałego Równania stałopunktowe Równania dziedzinowe Rekurencyjne równania dziedzinowe Rekurencyjne równania dziedzinowe Problemy Dziedziny refleksywne Rozwiązanie naiwne dziedziny Scotta

Pełne rozwiązanie problemu definiowania dziedzin semantycznych w dowolnie rekurencyjny sposób zostało przedstawione przez Scotta kilka lat po jego pierwszej konstrukcji dziedziny refleksywnej. Nie będziemy tu przedstawiać szczegółów; wszystkie te rozwiązania wymagają wykorzystania nie zawsze naturalnego kodowania czy to funkcji, czy to samych dziedzin jako elementów dziedzin.

Z grubsza, rozwiązania te polegają na dalszym ograniczeniu pojęcia dziedziny semantycznej: nie są to już dowolne zbiory łańcuchowo zupełne. Ogranicza się ich rozmiar przez wprowadzenie dodatkowego wymagania, by każdy element był kresem górnym podzbioru wyróżnionego przeliczalnego zbioru elementów bazowych, oraz dodatkowych założeń technicznych, pozwalających utożsamiać elementy ze zbiorami elementów bazowych, które je aproksymują. Operatory na takich dziedzinach wprowadza się jak powyżej; kluczowe jest tu jednak ograniczenie się do rozważania jedynie funkcji ciągłych. Definiuje się następnie "dziedzinę wszystkich dziedzin", której elementy kodują dowolną, spełniającą powyższe warunki dziedzinę. Na dziedzinie tej z kolei określa się pewne funkcje ciągłe, które odpowiadają podstawowym operatorom konstruowania dziedzin (w tym dziedziny funkcji). Teraz równania dziedzinowe to "po prostu" równania stałopunktowe w tej dziedzinie wszystkich dziedzin, a istnienie ich najmniejszych rozwiązań zapewnia zwykłe twierdzenie o istnieniu najmniejszych punktów stałych dla funkcji ciągłych. Pierwsza konstrukcja Scotta definiowała kluczową tu "dziedzinę wszystkich dziedzin" na zbiorze podzbiorów liczb naturalnych; kolejne konstrukcje wykorzystywały drzewa liczb naturalnych, systemu informacyjne, i inne. Dokładniejsze omówienie tej niezwykle ciekawej tematyki i pouczającej historii rozwoju "teorii dziedzin Scotta" wykracza jednak poza zakres tych zajęć.