Teoria do domínio - Domain theory

A teoria dos domínios é um ramo da matemática que estuda tipos especiais de conjuntos parcialmente ordenados (posets) comumente chamados de domínios . Consequentemente, a teoria de domínio pode ser considerada um ramo da teoria da ordem . O campo tem grandes aplicações em ciência da computação , onde é usado para especificar a semântica denotacional , especialmente para linguagens de programação funcionais . A teoria do domínio formaliza as idéias intuitivas de aproximação e convergência de uma maneira muito geral e está intimamente relacionada à topologia .

Motivação e intuição

A principal motivação para o estudo de domínios, iniciado por Dana Scott no final dos anos 1960, foi a busca por uma semântica denotacional do cálculo lambda . Nesse formalismo, considera-se "funções" especificadas por certos termos da linguagem. De uma forma puramente sintática , pode-se ir de funções simples a funções que tomam outras funções como seus argumentos de entrada. Usando novamente apenas as transformações sintáticas disponíveis neste formalismo, pode-se obter os chamados combinadores de ponto fixo (o mais conhecido dos quais é o combinador Y ); estes, por definição, têm a propriedade de que f ( Y ( f )) = Y ( f ) para todas as funções f .

Para formular tal semântica denotacional, pode-se primeiro tentar construir um modelo para o cálculo lambda, no qual uma função genuína (total) está associada a cada termo lambda. Tal modelo formalizaria uma ligação entre o cálculo lambda como um sistema puramente sintático e o cálculo lambda como um sistema de notação para manipular funções matemáticas concretas. O cálculo combinador é esse modelo. No entanto, os elementos do cálculo combinador são funções de funções para funções; para que os elementos de um modelo do cálculo lambda tenham domínio e alcance arbitrários, eles não poderiam ser funções verdadeiras, apenas funções parciais .

Scott contornou essa dificuldade formalizando uma noção de informação "parcial" ou "incompleta" para representar cálculos que ainda não retornaram um resultado. Isso foi modelado considerando, para cada domínio de computação (por exemplo, os números naturais), um elemento adicional que representa uma saída indefinida , ou seja, o "resultado" de uma computação que nunca termina. Além disso, o domínio da computação está equipado com uma relação de ordenação , na qual o "resultado indefinido" é o menor elemento .

A etapa importante para encontrar um modelo para o cálculo lambda é considerar apenas as funções (em tal conjunto parcialmente ordenado) que garantem ter menos pontos fixos . O conjunto dessas funções, junto com uma ordenação apropriada, é novamente um "domínio" no sentido da teoria. Mas a restrição a um subconjunto de todas as funções disponíveis tem outro grande benefício: é possível obter domínios que contêm seus próprios espaços de funções , ou seja, obtém-se funções que podem ser aplicadas a eles próprios.

Além dessas propriedades desejáveis, a teoria do domínio também permite uma interpretação intuitiva atraente. Conforme mencionado acima, os domínios de computação são sempre parcialmente ordenados. Essa ordenação representa uma hierarquia de informações ou conhecimento. Quanto mais alto um elemento está no pedido, mais específico ele é e mais informações ele contém. Os elementos inferiores representam conhecimento incompleto ou resultados intermediários.

A computação então é modelada aplicando funções monótonas repetidamente em elementos do domínio para refinar um resultado. Alcançar um ponto fixo equivale a terminar um cálculo. Os domínios fornecem uma configuração superior para essas idéias, uma vez que pontos fixos de funções monótonas podem existir e, sob restrições adicionais, podem ser aproximados de baixo para cima.

Um guia para as definições formais

Nesta seção, os conceitos e definições centrais da teoria de domínio serão introduzidos. A intuição acima de domínios sendo ordenações de informação será enfatizada para motivar a formalização matemática da teoria. As definições formais precisas podem ser encontradas nos artigos dedicados a cada conceito. Uma lista de definições gerais da teoria da ordem, que também incluem noções teóricas do domínio, pode ser encontrada no glossário da teoria da ordem . Os conceitos mais importantes da teoria de domínio, no entanto, serão apresentados a seguir.

Conjuntos direcionados como especificações convergentes

Como mencionado antes, a teoria de domínio lida com conjuntos parcialmente ordenados para modelar um domínio de computação. O objetivo é interpretar os elementos de tal ordem como pedaços de informação ou resultados (parciais) de um cálculo , onde os elementos que estão mais altos na ordem estendem a informação dos elementos abaixo deles de forma consistente. Desta simples intuição já fica claro que os domínios muitas vezes não possuem um elemento maior , pois isso significaria que existe um elemento que contém a informação de todos os outros elementos - uma situação bastante desinteressante.

Um conceito que desempenha um papel importante na teoria é o de um subconjunto direcionado de um domínio; um subconjunto direcionado é um subconjunto não vazio da ordem em que quaisquer dois elementos têm um limite superior que é um elemento desse subconjunto. Em vista de nossa intuição sobre domínios, isso significa que quaisquer duas informações dentro do subconjunto direcionado são consistentemente estendidas por algum outro elemento do subconjunto. Portanto, podemos ver os subconjuntos direcionados como especificações consistentes , ou seja, como conjuntos de resultados parciais nos quais não há dois elementos contraditórios. Essa interpretação pode ser comparada com a noção de uma sequência convergente em análise , onde cada elemento é mais específico que o anterior. De fato, na teoria dos espaços métricos , as sequências desempenham um papel que é em muitos aspectos análogo ao papel dos conjuntos direcionados na teoria do domínio.

Agora, como no caso das sequências, estamos interessados ​​no limite de um conjunto dirigido. De acordo com o que foi dito acima, este seria um elemento que é a informação mais geral que estende a informação de todos os elementos do conjunto direcionado, ou seja, o elemento único que contém exatamente a informação que estava presente no conjunto direcionado, e nada mais. Na formalização da teoria da ordem, este é apenas o menor limite superior do conjunto direcionado. Como no caso de limites de sequências, os limites superiores mínimos de conjuntos direcionados nem sempre existem.

Naturalmente, alguém tem um interesse especial naqueles domínios de computação nos quais todas as especificações consistentes convergem , isto é, em ordens nas quais todos os conjuntos direcionados têm um limite superior mínimo. Esta propriedade define a classe de pedidos parciais completos direcionados , ou dcpo para abreviar. De fato, a maioria das considerações da teoria do domínio considera apenas pedidos que são pelo menos direcionados completos.

Da ideia subjacente de resultados parcialmente especificados como representativos de conhecimento incompleto, derivam-se outra propriedade desejável: a existência de um elemento mínimo . Tal elemento modela esse estado de ausência de informação - o lugar onde a maioria dos cálculos começa. Ele também pode ser considerado como a saída de um cálculo que não retorna nenhum resultado.

Computações e domínios

Agora que temos algumas descrições formais básicas do que deve ser um domínio de computação, podemos nos voltar para os próprios cálculos. Claramente, essas têm que ser funções, pegando entradas de algum domínio computacional e retornando saídas em algum domínio (possivelmente diferente). No entanto, também se esperaria que a saída de uma função contenha mais informações quando o conteúdo de informação da entrada for aumentado. Formalmente, isso significa que queremos que uma função seja monotônica .

Ao lidar com dcpos , pode-se também querer que os cálculos sejam compatíveis com a formação de limites de um conjunto direcionado. Formalmente, isso significa que, para alguma função f , a imagem f ( D ) de um conjunto direcionado D (ou seja, o conjunto das imagens de cada elemento de D ) é novamente direcionado e tem como limite superior mínimo a imagem do mínimo limite superior de D . Também se poderia dizer que f preserva a suprema dirigida . Observe também que, ao considerar conjuntos direcionados de dois elementos, tal função também deve ser monotônica. Essas propriedades dão origem à noção de uma função contínua de Scott . Como isso geralmente não é ambíguo, também se pode falar de funções contínuas .

Aproximação e finitude

A teoria do domínio é uma abordagem puramente qualitativa para modelar a estrutura dos estados de informação. Pode-se dizer que algo contém mais informações, mas a quantidade de informações adicionais não é especificada. No entanto, existem algumas situações em que se deseja falar sobre elementos que são, em certo sentido, muito mais simples (ou muito mais incompletos) do que um determinado estado de informação. Por exemplo, na ordem de inclusão de subconjunto natural em algum conjunto de poderes , qualquer elemento infinito (isto é, conjunto) é muito mais "informativo" do que qualquer um de seus subconjuntos finitos .

Se alguém deseja modelar tal relacionamento, pode primeiro considerar a ordem estrita induzida <de um domínio com ordem ≤. No entanto, embora essa seja uma noção útil no caso de pedidos totais, ela não nos diz muito no caso de conjuntos parcialmente ordenados. Considerando novamente as ordens de inclusão de conjuntos, um conjunto já é estritamente menor que outro, possivelmente infinito, se contiver apenas um elemento a menos. No entanto, dificilmente se concordaria que isso captura a noção de ser "muito mais simples".

Relação abaixo

Uma abordagem mais elaborada leva à definição da chamada ordem de aproximação , que é mais sugestivamente também chamada de relação caminho-abaixo . Um elemento x está muito abaixo de um elemento y , se, para cada conjunto dirigido D com supremo tal que

,

há algum elemento d em D tal que

.

Então, também se diz que x se aproxima de y e escreve

.

Isso implica que

,

uma vez que o conjunto singleton { y } é direcionado. Por exemplo, em uma ordenação de conjuntos, um conjunto infinito está muito acima de qualquer um de seus subconjuntos finitos. Por outro lado, considere o conjunto direcionado (na verdade, a cadeia ) de conjuntos finitos

Uma vez que o supremo desta cadeia é o conjunto de todos os números naturais N , isto mostra que nenhum conjunto infinito é abaixo N .

No entanto, estar muito abaixo de algum elemento é uma noção relativa e não revela muito sobre um elemento sozinho. Por exemplo, gostaríamos de caracterizar conjuntos finitos de uma forma teórica de ordem, mas mesmo conjuntos infinitos podem estar muito abaixo de algum outro conjunto. A propriedade especial desses elementos finitos x é que eles estão muito abaixo de si mesmos, ou seja,

.

Um elemento com essa propriedade também é chamado de compacto . No entanto, esses elementos não precisam ser "finitos" nem "compactos" em qualquer outro uso matemático dos termos. A notação é, no entanto, motivada por certos paralelos com as respectivas noções na teoria dos conjuntos e topologia . Os elementos compactos de um domínio têm a propriedade especial importante de não poderem ser obtidos como limite de um conjunto dirigido no qual ainda não ocorreram.

Muitos outros resultados importantes sobre a relação do caminho abaixo apóiam a afirmação de que essa definição é apropriada para capturar muitos aspectos importantes de um domínio.

Bases de domínios

As reflexões anteriores levantam outra questão: é possível garantir que todos os elementos de um domínio possam ser obtidos como um limite de elementos muito mais simples? Isso é bastante relevante na prática, uma vez que não podemos computar objetos infinitos, mas ainda podemos esperar aproximá-los arbitrariamente.

De maneira mais geral, gostaríamos de restringir a um determinado subconjunto de elementos como sendo suficiente para obter todos os outros elementos como limites superiores mínimos. Assim, define-se uma base de um poset P como sendo um subconjunto B de P , de forma que, para cada x em P , o conjunto de elementos em B que estão bem abaixo de x contém um conjunto direcionado com supremo x . O poset P é um poset contínuo se tiver alguma base. Especialmente, o próprio P é uma base nesta situação. Em muitas aplicações, restringe-se a contínua (d) cpos como objeto principal de estudo.

Finalmente, uma restrição ainda mais forte em um conjunto parcialmente ordenado é dada exigindo a existência de uma base de elementos finitos . Esse poset é denominado algébrico . Do ponto de vista da semântica denotacional, os posets algébricos são particularmente bem-comportados, pois permitem a aproximação de todos os elementos mesmo quando se restringem a elementos finitos. Como observado antes, nem todo elemento finito é "finito" no sentido clássico e pode muito bem ser que os elementos finitos constituam um conjunto incontável .

Em alguns casos, no entanto, a base de um poset é contável . Neste caso, fala-se de um poset ω-contínuo . Conseqüentemente, se a base contável consiste inteiramente em elementos finitos, obtemos uma ordem que é ω-algébrica .

Tipos especiais de domínios

Um caso especial simples de domínio é conhecido como domínio elementar ou plano . Consiste em um conjunto de elementos incomparáveis, como os inteiros, junto com um único elemento "inferior" considerado menor do que todos os outros elementos.

Pode-se obter uma série de outras classes especiais interessantes de estruturas ordenadas que podem ser adequadas como "domínios". Já mencionamos posets contínuos e posets algébricos. Versões mais especiais de ambos são cpos contínuos e algébricos . Adicionando ainda mais propriedades de completude, obtém-se reticulados contínuos e reticulados algébricos , que são apenas reticulados completos com as respectivas propriedades. Para o caso algébrico, encontramos classes mais amplas de posets que ainda valem a pena estudar: historicamente, os domínios de Scott foram as primeiras estruturas a serem estudadas na teoria dos domínios. Ainda as classes mais amplas de domínios são constituídos por SFP-domínios , L-domínios , e domínios bifinite .

Todas essas classes de ordens podem ser convertidas em várias categorias de dcpos, usando funções que são monótonas, contínuas de Scott ou até mais especializadas como morfismos . Finalmente, observe que o termo domínio em si não é exato e, portanto, só é usado como uma abreviatura quando uma definição formal foi dada antes ou quando os detalhes são irrelevantes.

Resultados importantes

Um poset D é um dcpo se e somente se cada cadeia em D tiver um supremo. (A direção 'se' depende do axioma de escolha .)

Se f é uma função contínua em um domínio D, então ela tem um ponto mínimo fixo, dado como o menor limite superior de todas as iterações finitas de f no menor elemento ⊥:

.

Este é o teorema do ponto fixo de Kleene . O símbolo é a junção direcionada .

Generalizações

  • "Teoria do domínio sintético". CiteSeerX   10.1.1.55.903 . Citar diário requer |journal= ( ajuda )
  • Teoria do domínio topológico
  • Um espaço de continuidade é uma generalização de espaços métricos e posets , que podem ser usados ​​para unificar as noções de espaços e domínios métricos.

Veja também

Leitura adicional

links externos