Existem várias maneiras de explicar "computável implica contínuo"; darei aqui duas dessas explicações.
Máquinas de Turing calculam mapas contínuos
Suponha que tenhamos uma máquina de Turing que absorve uma quantidade infinita de entradas gravadas em uma fita de entrada. Ele grava o resultado em uma fita de saída, onde as células de saída são gravadas uma vez. Existem fitas de sinal de trabalho. A máquina pode funcionar para sempre, preenchendo as células de saída. Isso é conhecido como uma máquina do tipo dois . (O argumento para outros tipos de máquinas será semelhante, mas mais simples.)
O seguinte deve ser óbvio: quando a máquina grava em uma célula de saída, seu funcionamento até esse ponto depende apenas de uma parte finita da fita de entrada, pelo simples motivo de que, em finitas etapas da computação, não poderia ter movido a cabeça de entrada passado algum ponto. Portanto, toda fita de entrada que esteja de acordo com a fita especificada até aquele momento faria com que a máquina escrevesse a mesma resposta na mesma célula de saída.
Mas essa é uma forma de continuidade, se colocarmos a topologia correta nos espaços das fitas de entrada e saída.
Primeiro, colocamos a topologia no conjunto dos símbolos que podem ser gravados nas células da fita. Para isso, basta escolher a topologia discreta. Uma fita é uma sequência infinita de símbolos, portanto, um elemento de , que é um produto de 's. Vamos colocar a topologia do produto.ΣΣωΣ
Lembre-se de que um conjunto aberto básico em para a topologia do produto tem o formato , em que . Ou seja, um conjunto aberto básico fixa uma parte inicial da sequência aos valores fornecidos .ΣωU(a0,…,an−1)={α∈Σω∣∀i<n.αi=ai}a0,…,ai∈Σa0,…,an
Agora podemos verificar se a função calculada pela máquina é realmente contínua. Tome um conjunto aberto básico e deixe . Precisamos verificar se está aberto. Para este fim, considerar qualquer . Se encontrarmos um conjunto aberto básico tal que , então terminamos.f:Σω→ΣωV=U(a0,…,an−1)W=f−1(V)Wα∈WW′α∈W′⊆W
Porque , temos . Assim, na entrada a máquina produz uma fita de saída começando com . No momento em que grava essas células, ele inspeciona no máximo as primeiras células da entrada, em busca de alguns . Podemos tomar e verificar se . É óbvio que . Para provar tomar qualquer e observar que e concordam com a primeiraα∈Wf(α)∈Uαa0,a1,…,an−1kk∈NW′:=U(α0,…,αk)α∈W′⊆Wα∈W′W′⊆Wβ∈W′f(α)f(β)n valores da saída. Isso implica que e, portanto, , conforme necessário.f(β)∈Vβ∈W
Mapas computáveis são contínuos como mapas entre CPOs algébricasω
Primeiro, deixe-me observar que o que você definiu geralmente é chamado de " CPO" ( no nome indica que precisamos apenas de supremacia de cadeias).ωω
Na semântica denotacional, os tipos de dados correspondem a CPOs. De fato, eles correspondem a CPOs algébricas (isso está em sua tese?), Que são CPOs para os quais os elementos compactos formam uma base. Aqui estão algumas definições.ω ωω
Definição: Seja um CPO . Um elemento é compacto se, para cada cadeia tal que , existe tal que .Dωd∈Dx0≤x1≤⋯d≤⨆ixijd≤xj
Definição: Um CPO é algébrico se todo for o supremo de elementos compactos abaixo dele.ωx∈D
A intuição por trás dos elementos compactos é que eles contêm "informações finitas". Um bom exemplo é , o conjunto de números naturais ordenados por , onde os elementos compactos são precisamente os subconjuntos finitos de (exercício!). Outro exemplo: no CPO de funções contínuas os elementos compactos são aquelas funções parciais que são iguais a todos os lugares, exceto em muitos argumentos finitos.P(N)⊆NωN→N⊥⊥
Dizer que um CPO é algebrico é dizer que todo elemento é completamente determinado pelas informações finitas que o aproximam. É fato que, na semântica denotacional, os tipos de dados correspondem aos CPOs algébricos , a menos que estejamos fazendo algo muito incomum.ωω
Agora podemos explicar por que todo mapa computável é contínuo. Suponha que e sejam CPOS computáveis. Suponha que , , é compacto e . Intuitivamente, isso diz que "informações finitas aparecem na saída ". Como é computável, deve-se calcular as informações acessando apenas uma quantidade finita de informações sobre , ou seja, existe um compacto tal que eDEωf:D→Ex∈De∈Eee≤f(x)ef(x)fexd∈Dd≤xe≤f(d) . Este argumento deve ser comparado ao argumento da máquina de Turing acima. Nós estabelecemos:
Lema: Se é computável e para alguns e um compacto , então existe um compacto tal que e .f:D→Ee≤f(x)x∈De∈Ed∈Dd≤xe≤f(d)
Podemos usar o lema para mostrar que um computável é contínuo. Suponha é uma cadeia em . Como é monótono, já sabemos que , mas também precisamos da desigualdade . Como é algébrico, basta mostrar que, sempre que é compacto e então . Portanto, assuma . Pelo lema, existe um compacto tal quefx0≤x1≤⋯Df⨆if(xi)≤f(⨆ixi)f(⨆ixi)≤⨆if(xi)Ee∈Ee≤f(⨆ixi)e≤⨆if(xi)e≤f(⨆ixi)d∈Dd≤⨆ixi e . Como é compacto, existe tal que , portanto, pela monotonicidade de , temos . Acabamos.e≤f(d)djd≤xjfe≤f(d)≤f(xj)≤⨆if(xi)
